[ 백준 11055 ] - 가장 큰 증가 부분 수열 (Kotlin)
알고리즘/백준·2023. 2. 11.
11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 이해 & 기본 개념 수열에서 증가하는 부분 (이어질 필요 x)에서 가장 합이 큰 경우를 찾아야하는 문제 중요 포인트 모든 경우의 수를 보는 방법도 있긴 하겠지만, 중복된 연산이 많이 발생 중복된 연산을 줄이기 위해 dp를 사용하면 간단하게 풀 수 있음 최종 풀이 점화식 dp[i] = max(dp[i], dp[j] + a[i]) i는 현재 위치, j는 이전에 선택된 원소의 위치 dp[i]는 i까지의 최..