[Codility] Lesson9. MaxSliceSum (Python)

1. 문제

https://app.codility.com/c/run/training2B63MW-T7C/

Codility

 

2. 풀이

테스트케이스 1개가 안풀려서 답을 찾아봤던 문제.

이 문제의 해결 포인트는 합이 음수가 나오기 전까지 계속 합을 더해주고, 음수가 나오면 그 다음 수부터 다시 누적합을 구하면된다.

왜냐하면 현재 음수보다 이전의 합이 더 작으면 앞으로 누적합을 더해도 합이 음수이기 때문에 그 만큼 합계가 작아지기 때문이다.

 

3. 코드

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_sum =  -1000000
    max_part_sum = 0

    for n in A:
        max_sum = max(max_sum, max_part_sum + n)
        max_part_sum = max(0, max_part_sum + n)
    return max_sum

참고

https://nukeguys.tistory.com/188