[알고리즘] 가장 큰 부분배열의 합 (카데인 알고리즘, 다이나믹 프로그래밍)

관련 문제 링크 : 

leetcode.com/problems/maximum-subarray/

leetcode.com/problems/gas-station/

 

다른 다이나믹 프로그래밍 문제 :

leetcode.com/problems/best-time-to-buy-and-sell-stock/

 

이문제의 핵심은 각각의 부분합을 구할 때 현재 위치 이전까지의 결과가 반영된다는 것을 이해하는 것이다.

 

예를들어 -3이 있는 index 2까지의 부분합을 구할 때 우리는 이전 index 들인 -2 와 1 의 합에 현재 index 2의 값 -3을 더함으로써 쉽게 index 2 까지의 부분합을 구할 수 있다. 그리고 그다음 index인 4까지의 부분합을 구할 때 또 -3까지의 부분합에 4를 더하여 쉽게 구할 수 있다.

 

 

이 문제는 최대 부분합을 구하는 것인데, 그렇다면 이전까지의 부분합 + 현재위치의 값과 그냥 현재위치의 값을 비교하여서 만약 지금까지의 부분합에 현재위치의 값을 더한것이 현재위치의 값보다 더 작다면 부분합을 리셋하고 해당 index 부터 다시 계산을 시작하면 된다.

예를 들어 위의 array에 index 0 에는 -2가 index 1 에는 1이 있다. -2 와 1 을 더한 값 -1 은 index 1 의 값 1 보다 작다. 그렇다면 최대 부분합에 index 0은 들어가지 않는다는 의미다. index 0을 포함하지않아야 부분합이 더 커질 수 있기 때문이다.

 

이러한 논리는 큰문제를 작은 문제로 쪼개어 해결하고 한번 풀었던 문제를 다시 풀지 않게 하는 다이나믹 프로그래밍의 특징이다.

 

오히려 코드가 정말 단순해서 이해하기가 어려웠다....😂 (이게 정말 된다고? 아리송했었음..)

카데인 알고리즘은 O(n) 이다.