Dynamic Programming - Maximum Subarray

Maximum Subarray

• 배열에서 연속된 부분 배열중 그 합이 가장 큰 부분 배열을 찾는 문제.
• 값으로는 양수, 음수 존재.
• 배열의 값이 모두 음수 값이라면, 그 중 절댓값이 가장 작은 값이 정답.
  (공집합(아무런 부분 배열도 고르지 않음)은 정답에서 제외한다.)

---

O(n³) 알고리즘

브루트포스

가능한 모든 배열을 찾는다.

---

O(n²) 알고리즘

구하는데 겹치는 부분은 이전 것을 재활용한다.

---

O(n) 알고리즘

방법 1 : i를 포함한 최대합과 포함하지 않은 최대합을 비교한다.
DP1[k] = Max(DP1[k-1] + arr[k], arr[k]) // DP1은 i를 포함하지 않은 최대합이다.
DP2[k] = Max(DP1[k], DP2[k-1]) // DP2는 i를 포함한 최대합이다.

i=1 부터 시작해서 모든 i에 대해서 구해본다.
마지막 DP2 에서의 비교를 통해 큰 값이 정답.

방법 2 : Prefix Sum
Prefix Sum : 현재 까지의 합 (최대 합 아님.)
Min : 현재 까지의 Prefix Sum에서 가장 최소였던 값

배열을 전부다 순회했을 때 Prefix Sum과 Min 의 차이가 가장 큰 것이 정답이다.
(Min 자체가 Prefix Sum으로 부터 구해진 값이기 때문.)