[python] Codility Lesson 9-3. MaxDoubleSliceSum

 

 

슬라이싱이 이쁘장하게 되지않고 각각 애매하게 슬라이딩 되서 Y값이 빠지는 부분은 어떻게 하지, 각각을 어떻게 따로 구해서 더하나?

한번에 할방법 없나 이런생각 저런생각하다 "구글링 했습니다..." (출처 : https://curt-park.github.io/2018-09-14/algorithm-max-double-slice-sum/)

 

1. 좌측 slice를 구해주는데, 저번 문제처럼 l_max_slice_sum[i-1] + A[i]

 

아래와 같이 보면 이해할 수 있지만 아래와 같이 깔끔하게 생각해 내는게 쉽지 않은 것 같다.

 

 

1. l_max_slice_sum 과 r_max_slice_sum을 len(A)크기의 리스트로 생성하자.

 

2. X,Y,Z 중 Y를 i+1로 두고 for문을 돌려서 l_max_slice_sum리스트를 각각 최대값으로 할당해주자. (l_max_slice_sum[i-1]+ A[i] 음수이면 0을 할당해주는 것을 이해하는게 가장 중요한듯)

 

3. 마찬가지로 for문의 범위에 유의하며 r_max_slice_sum 리스트들의 원소를 채워주자. (i 가 감소하며 값을 할당해줌)

 

4. (X,Y,Z)의 경우의수를 for문 한번을 돌면서 다 처리해주면서 max_slice_sum을 갱신해주며 값을 구한다.

 

def solution(A):
    l_max_slice_sum = [0] * len(A)
    r_max_slice_sum = [0] * len(A)

    for i in range(1, len(A)-2): # A[X + 1] + A[X + 2] + ... + A[Y − 1]
        # Let's assume that Y is equal to i+1.
        # If l_max_slice_sum[i-1] + A[i] is negative, we assign X to i.
        # It means that the slice sum is 0 because X and Y are consecutive indices.
        l_max_slice_sum[i] = max(l_max_slice_sum[i-1] + A[i], 0)

    for i in range(len(A)-2, 1, -1): # A[Y + 1] + A[Y + 2] + ... + A[Z − 1]
        # We suppose that Y is equal to i-1.
        # As aforementioned, Z will be assigned to i if r_max_slice_sum[i+1] + A[i]
        # is negative, and it returns 0 because Y and Z becomes consecutive indices.
        r_max_slice_sum[i] = max(r_max_slice_sum[i+1] + A[i], 0)

    max_slice_sum = l_max_slice_sum[0] + r_max_slice_sum[2]
    for i in range(1, len(A)-1):
        # Let's say that i is the index of Y.
        # l_max_slice_sum[i-1] is the max sum of the left slice, and
        # r_max_slice_sum[i+1] is the max sum of the right slice.
        max_slice_sum = max(max_slice_sum, l_max_slice_sum[i-1]+r_max_slice_sum[i+1])
        
    return max_slice_sum