📡Kadane's Algorithm

🔊 주어진 배열에서 '부분연속수열합'의 최댓값을 구하는 알고리즘이다. DP로도 구할 수 있고, well-known Kadane's Algorithm을 활용해서도 매우 간단히 해결할 수 있다.

 

🔊 각 element traversing할 때마다 max() 두 번 사용. max_till_now로 최종 최댓값 update하고, cur_max는 현재위치의 원소 only & 현재위치의 원소 포함 그 전의 cur_max 합 두 개중 최댓값 update. 즉 cur_max로 각 원소를 포함한 부분연속수열합 최댓값을 계속 구해나가는 dp 방식이나 마찬가지. 다만, dp는 최종적으로 max() 한 번 사용이지만, Kadane's algorithm에서는 max()를 그 때 그 때 update하는 방식만 차이점. 핵심은 '현재 위치의 원소는 무조건 부분합에 포함된 상태에서 나 자신만 고려하는게 더 큰 지, 아니면 앞선 최댓값에 나 자신을 더한 결과가 큰 지'를 확인. 첫 cur_max는 0으로 설정. max_till_now는 문제에서 주어진 범위에 따라 전체 array의 최솟값으로 설정

 

🔊 BOJ 1912 <연속합> 실버2 & LeetCode 53 <Maximum Subarray> 문제 참고.

 

🔊 python

import math
#list nums
def maxSubArray(self, nums: List[int]) -> int:
    ans,curmax=-math.inf,0
    for i in range(len(nums)):
        curmax=max(curmax+nums[i],nums[i])
        ans=max(ans,curmax)
    return ans