[Codility] 9.3 MaxSliceSum

MaxSliceSum
Maximum subarray, Maximum subsequence sum이라고 알려져있는 문제이다. 워낙 유명하니 반드시 익혀두자.
재귀식 $S[i] = \max(0, S[i-1] + A[i])$을 이용하면 된다.
하지만 이 재귀식은 답이 음수(모든 원소가 음수인 경우)인 경우를 해결할 수 없다. (S = 0이 된다)
$S[i]$가 업데이트 될 때마다 마지막 인덱스 end도 업데이트하고, end의 값이 초기값과 같다면 모든 원소가 음수이므로 다시 반복문을 돌려서 최댓값을 찾는다.
kadane's Algorithm을 이용하면 어느 subarray(subsequence, slice)인지도 찾아낼 수 있다.
Wikipidia의 알고리즘
GeeksforGeeks의 kadane's algorithm

def solution(A):
    if len(A) == 1:
        return A[0]

    N = len(A)
    max_sum, cur_sum = 0, 0
    start, end = -1, -1
    cur_start = 0
    for i in range(N):
        cur_sum += A[i]
        if max_sum < cur_sum:
            max_sum = cur_sum
            start = cur_start
            end = i
            cur_start = i + 1
        elif cur_sum < 0:
            cur_sum = 0
            
    
    if end == -1:
        max_sum = A[0]
        for i in range(1, N):
            if max_sum < A[i]:
                max_sum = A[i]
                start = end = i

    return max_sum