Kadane's Algorithm

참조 : https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d
참조 : https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass

관련 문제 : LeetCode No.53 (https://leetcode.com/problems/maximum-subarray/)
관련 문제 : LeetCode No.918 (https://leetcode.com/problems/maximum-sum-circular-subarray/)

• 한줄요약을 하자면, 수 배열중 합이 최대가 되는 Subarray를 구하는 알고리즘이다.
• Subarray : 연속된 인덱스를 가진 부분배열이다.
• 다이나믹 프로그래밍의 일종이다. 어떤 배열에 대해 Subarray의 합의 최댓값을 구할 때 사용한다.
• 만약 이 문제를 고전적인 완전 탐색 방법으로 푼다면, O(n^2)의 시간 복잡도를 갖는다. 각 인덱스의 원소에 대해 해당 인덱스에서 출발하여 얻어낼 수 있는 Subarray의 합 중 최댓값을 기록하고, 그것을 모든 인덱스에 대해 수행해야 한다.
• Kadane's Algorithm(카데인 알고리즘)은, 어떤 인덱스의 수까지의 Subarray의 합은, 그 이전 인덱스까지의 합에 해당 인덱스의 수를 더하면 나온다는 개념에서 출발한다. Prefix Sum에서도 비슷한 내용이 나왔었지.
• nums라는 배열에 이를 적용한다고 가정하자. 먼저 currMax라는 변수를 두고, 매 인덱스마다 지금까지의 합에 새로운 인덱스의 값을 더할 것인지, 아니면 새로운 인덱스의 값부터 다시 합을 계산하기 시작할지를 결정한다. currMax = max(nums[i], currMax + nums[i])
• 동시에 maximum 변수를 지정해, 부분합의 최댓값을 모니터링한다. maximum = max(maximum, currMax)
• 이후 마지막에 maximum 값을 반환하면 된다.
• 이 경우 시간복잡도는 O(n)이다. 배열을 한 번만 순회하기 때문.
• 간혹 Circular array에서 Subarray의 최댓값을 구하라고 할 수도 있다. 이 때는, 배열의 전체 요소의 합에서 minimum subarray의 합을 빼 주는 것이 maximum subarray의 합과 일치한다. 단! maximum 값이 0보다 클 경우에만.