[백준/Python] 11055번: 가장 큰 증가 부분 수열

11055번: 가장 큰 증가 부분 수열 (acmicpc.net)

11055번: 가장 큰 증가 부분 수열

---

문제 해석

수열 A의 부분수열 중 제일 합이 큰 부분수열의 합을 구한다.

---

코드

---

문제 풀이

예제로 나온 "가장 긴 증가하는 부분 수열"과 비슷한 문제이다.

n과 a에 input 값들을 넣어주고 누적합을 구하기 위한 list b를 선언해주었다. 그리고 b는 최소 자기자신을 더한 값이 나오므로 a의 값을 그대로 b로 옮겨주었다.

n이 최대 1000까지 이므로 O(n^2)을 하여도 1,000,000밖에 나오지 않기 떄문에 이중for문을 이용했다. 수열이므로 a[i]가 그 이전의 a 요소 보다 크다면 이전 부분수열의 누적합인 b[j]와 a[i]의 합과, 현재 누적합인 b[i] 중 큰 값을 b[i]에 저장해주었다.

해당 연산을 수행 후 max(b)를 출력하면 최대 누적합이 나오게 된다.