Kadane Algorithm

Maximum Sum Subarray라 불리는 문제에서 슬라이딩 윈도우기법으로 O(N)에 해결하는 알고리즘

Maximum Sum Subarray란 수열의 연속 부분합중 가장 큰 값을 찾는 문제

Kadane Algorithm을 간략히 설명하자면

1. 앞에서부터 수를 하나씩 더해가면서 sum이라는 변수에 매번 값을 저장한다.

2. 만약 sum이 음수가 되는 지점이 발생한다면, sum은 0으로 초기화한다.

3. 이 sum들을 매번 maximum값으로 갱신한다.

구간의 index가 필요하다면 sum을 갱신하는 부분에 추가하여 나타낼 수 있다.

위의 내용은 1-dim array에 관한 내용이고

이를 응용하면 2-dim array에서의 문제는 O(N^3)에 해결할 수 있다. (2차원 배열에서 최대 부분합)

참고영상 : https://youtu.be/yCQN096CwWM