[코딜리티] 파이썬 _ MaxDoubleSliceSum

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

MaxDoubleSliceSum coding task - Learn to Code - Codility

 

문제풀이 : 

어려웠던 문제다. 다른풀이를 참고해서 풀었다.

 

핵심은 Y를 기준으로 왼쪽의합과 오른쪽의 합을 구해서 이것의 최대를 구하는것이다.

N이 십만이므로 O(N)시간에 풀어야한다.

 

여기서 왼쪽합의 시작은 인덱스 0부터 하고, 오른쪽합의 시작은 인덱스 n-1 즉 맨 양쪽끝으로 잡는데 이렇게하면 배열길이가 8이라고할때 

(0,4,7)보다 (2,4,6) 이 더작을수도 있는데 이러면 시작이 양끝이아닌 2,6인데 이런건 어떻게 잡냐?

라는 의문이 든다.

 

근데 코드를 보면 이미 max(0, ~~) 이렇게 0과 비교하는 과정에서 걸러지게된다.

다시말해서 인덱스를 양쪽끝에서 시작해도 값을 더 작게만드는 부분은 무시되기 때문에 (2,4,6)이 더 작다면 그 인덱스로 계산된 값이 결과로 나오게된다.

 

정답코드 : 

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

def solution(A):
    # write your code in Python 3.6
    
    n = len(A)

    left_sum = [0]*n
    right_sum = [0]*n

    # 맨 처음과 마지막은 인덱스로서, 합산에 포함되지 않기때문에 1~N-1까지만 for문을 돈다.

    for i in range(1, n-1):
        left_sum[i] = max(0, left_sum[i-1]+A[i])
    
    for i in range(n-2, 0, -1):
        right_sum[i] = max(0, right_sum[i+1]+A[i])
    
    result = 0
    # left_sum[i] = 왼쪽끝부터 i까지의 합
    # right_sum[i] = 오른쪽끝부터 i까지의합 
    for i in range(1, n-1):
        result = max(result, left_sum[i-1]+right_sum[i+1])

    return result