카데인 알고리즘

카데인 알고리즘은 배열의 최대 부분 합을 O(n)의 시간복잡도로 구하는 알고리즘입니다.

개념을 간단하게 설명하자면, i번째 인덕세를 오른쪽 끝으로 하는 부분 배열들의 최대 부분 합을 M[i]라고 하면, M[i + 1]은 M[i] + arr[i + 1]이거나 arr[i + 1]중 더 큰 값입니다.

M[i + 1] = max(M[i] + arr[i + 1], arr[i + 1])인 이유는 i를 오른쪽 끝으로 하는 부분 배열 중 최대 부분 합이 음수이면 굳이 더하지 않고 그냥 i+1 번재 인덱스부터 새로 더하는 것이 이득이기 때문입니다.

참고: https://r4bb1t.tistory.com/10