(코딜리티) Lesson 9. [Maximum slice problem] : MaxDoubleSliceSum - python

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

MaxDoubleSliceSum coding task - Learn to Code - Codility

문제 내용

비어 있지 않은 N개의 배열 A가 주어질 때, 0<=X<Y<Z<N으로 슬라이스한 부분 합의 최대를 구하시오.

 

예를 들어, A = [3, 2, 6, -1, 4, 5, -1, 2]일 때,

X, Y, Z = (0, 3, 6)는 2+6+4+5 = 17

X, Y, Z = (0, 3, 7)는 2+6+4+5-1 = 16

X, Y, Z = (3, 4, 5)는 0

 

위와 같은 배열 A에서는 17을 return한다.

제한 사항

• N은 3~100,000
• A의 각 요소는 -10,000~10,000

코드

def solution(A):
    
    A_len = len(A)
    left_sum = [0]*A_len
    right_sum = [0]*A_len
	
    #제일 처음과 마지막은 합산하지 않기 때문에 1~N-1 까지만 for문을 돌게 합니다.
    for i in range(1, A_len-1):
    	# 0과 비교하여 큰 값을 배열에 넣으면, 값이 작아지는 경우는 합산 하지 않도록 합니다.
    	left_sum[i] = max(0, left_sum[i-1]+A[i])
	
    for i in range(A_len-1, 0, -1):
        right_sum[i-1] = max(0, right_sum[i]+A[i-1])

    m = 0
    for i in range(1, A_len-1):
        m = max(m, left_sum[i-1]+right_sum[i+1])

    return m

해설

for문 3개로 밖에 풀지 못하고, 위와 같은 코드는 다른 사람의 코드를 보고서도 이해하는 데 조금 오래걸린 문제네요..

 

X, Y, Z로 Y기준 좌측의 합, 우측의 합을 구하여 최종적으로 둘 다 더했을 때, 최댓값을 return하면 됩니다.

각각의 index는 합산 하지 않는 부분을 고려하고, 하나씩 더하면서, -로 떨어지는 경우는 0과 비교하여 0으로 채워넣습니다.

 

위와 같이 처리한다면, (2, 5, 7)와 (0, 5, 7) 중에 전자가 더 합이 클수도 있지 않나라고 생각할 수 있지만, 0과 비교하는 부분에서 알아서 걸러지기 때문에 이 부분까지 신경쓸 필요가 없게 됩니다.