[Codility] Lesson8. MaxDoubleSliceSum (Python)

1. 문제

https://app.codility.com/c/run/training7WK46H-9HS/

Codility

2.풀이

처음에 combination으로 만들수있는 인덱스(3개) 조합을 구하고 그 인덱스에 해당하는 합계를 구하니 시간초과가 났다  ㅜ,ㅜ

시간초과 해결 방법이 생각안나서 구글링으로 결국 해결,,,

전형적인 dp 알고리즘을 사용해서 풀어야하는 문제였다.

왼쪽-> 오른쪽 방향으로 배열의 누적 합을 미리 저장했었는데 왼쪽 <- 오른쪽 방향으로의 누적 합도 미리 저장해야하는 것이 포인트였다.

 

3. 코드

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

def solution(A):
    left_max_sum =[0] * len(A)
    right_max_sum = [0] * len(A)

    for i in range(1, len(A)-2):
        left_max_sum[i] = max(left_max_sum[i-1]+A[i], 0)
    for i in range(len(A)-2, 1, -1):
        right_max_sum[i] = max(right_max_sum[i+1]+A[i], 0)

    max_sum = left_max_sum[0] + right_max_sum[2] #(0,1,2)

    for i in range(1, len(A)-1):
        max_sum = max(max_sum, left_max_sum[i-1] + right_max_sum[i+1])
    return max_sum