[python] baekjoon 가장 큰 증가 부분 수열 문제 풀이
문제 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 수열 A가 주어졌을 때, 합이 가장 큰 증가 부분 수열의 합을 출력하시오. 문제풀이 수열의 크기는 최대 1000으로 주어진다. 가장 단순한 방법으로는 만들 수 있는 모든 수열을 만들어보고 증가 부분 수열 중 최댓값을 찾는 것이다. 하지만 이 방법은 O(2^1000)이라는 엄청난 시간이 걸린다. 이 문제는 부분문제로 쪼갠 뒤 해결할 수 있다. 현재 문제가 인덱스 i부터 시..
더보기