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

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

9. Maximum slice problem lesson - Learn to Code - Codility

문제 내용

비어 있지 않은 N개의 배열 A가 주어질 때, 0<=P<Q<N의 조건으로 (P, Q)슬라이스를 했을 때 최대 합을 찾으시오.

 

ex) A = [3, 2, -6, 4, 0]

P, Q = (3, 4)일 때, 4 + 0 = 4

P, Q = (2, 2)일 때, -6 

P, Q = (0, 1) 일 때, 5가 가장 크므로 5를 return한다.

제한 사항

• N은 1~1,000,000
• A의 각 요소는 -1,000,000~1,000,000
• 최종 결과는 -2,147,483,648~2,147,483,648 이다.

코드

def solution(A):
    
    #슬라이스 한 합을 위함
    slice_sum = [0]
    # 슬라이스 최대 합을 위함
    m = float('-inf')
    # a의 변수의 최대를 위함
    n = float('-inf')
	
    for a in A:
        c = slice_sum[-1] + a
		
        # 모든 값이 음수일 경우, 음수중에 가장 큰 값을 가져오기 위함
        if n < a:
            n = a
		
        # 슬라이스 합이 -로 갈경우는 0으로 초기화
        if c < 0:
            slice_sum.append(0)
        else :
            slice_sum.append(c)
            # 중간 중간 초기화가 되기때문에, 최댓값을 저장해놓기 위함
            if m < c:
                m = c
	
    # 모두 음수일 경우 0이 return되기 때문에 배열 A중에 가장 큰 요소 하나를 return
    return m if 0 < m else n

해설

MaxDoubleSliceSum에서 아이디어를 가져와서 풀었습니다.

 

배열 A를 차례대로 계속 더하다가 더한 값이 -로 갈경우 0으로 초기화 하고 최댓값은 이전에 저장해놨기 때문에 최종결과엔 지장이 없을 것입니다.

 

예를 들어, 

a = [3, 2, 2, -8, 1, 1, 1] 인 경우에 슬라이스 합은 

[3, 5, 7, 0, 1, 2, 3] 입니다. (0,2)인 7이 답이 될 것이고, 최대 값만 필요하므로 7만 저장해서 마지막에 return하면 됩니다.

 

또 한, a = [-6, -6, -6, -6, -1]인 경우에는,

위 알고리즘에서는 슬라이스 합이 [0, 0, 0, 0, 0]이 되므로, 배열 중에 가장 큰 값인 -1을 return하게 됩니다.

-1 대신 1이 들어가도 1이 return하게 되어있습니다.