Lesson 9: Maximum Slice Problem → Max Slice Sum

문제

MaxSliceSum coding task - Learn to Code - Codility

 

---

문제 풀이

Max Profit 문제와 동일하게 브루트 포스로 풀지 않고, 카데인 알고리즘 사용하면  쉽게 풀 수 있다.

 

---

코드

def solution(A):
    max_sum = sub_sum = A.pop(0)

    for num in A:
        sub_sum = max(sub_sum + num, num)
        max_sum = max(max_sum, sub_sum)

    return max_sum