[Codility] 9.3 MaxSliceSum

MaxSliceSum
Maximum subarray, Maximum subsequence sum이라고 알려져있는 문제이다. 워낙 유명하니 반드시 익혀두자.
재귀식 $S[i] = \max(0, S[i-1] + A[i])$

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