[codility] Lesson 9. Maximum slice problem - MaxSliceSum

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/

MaxSliceSum coding task - Learn to Code - Codility

 

 

• N개의 정수로 구성된 비어 있지 않은 배열 A가 제공될 때
• (P,Q)는 A[P] + A[P+1] + ... + A[Q]
• A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 4 A[4] = 0
• (3,4)의 합은 4 + 0 = 4 -> 4는 A의 slice
• A slice의 최대 값을 출력
• O(N)

 

def solution(A):
    res = float('-inf')
    sum = 0
    for a in A:
        sum = sum + a
        res = max(res, sum)
        sum = max(0, sum)
    return res