[Python 알고리즘] MaxSliceSum - Codility

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

---

문제

A non-empty array A consisting of N integers is given. 
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. 
The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write a function:
    def solution(A)
that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:
A[0] = 3  A[1] = 2  A[2] = -6
A[3] = 4  A[4] = 0

the function should return 5 because:
(3, 4) is a slice of A that has sum 4,
(2, 2) is a slice of A that has sum −6,
(0, 1) is a slice of A that has sum 5,
no other slice of A has sum greater than (0, 1).
Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..1,000,000];
each element of array A is an integer within the range [−1,000,000..1,000,000];
the result will be an integer within the range [−2,147,483,648..2,147,483,647].

문제 분석

Maximum slice 유형.

번역을 한다면 '배열에서 최대가 되는 부분합' 정도가 되겠다.

배열의 길이가 1,000,000 이하이므로 반드시 O(N) 이하의 시간복잡도로 풀어야 함.

 

배열의 원소의 범위는 [-1,000,000 ... -1,000,000] 이다.

Codility의 교육 자료에 있는 O(N)으로 풀이하려 했으나, 추가적으로 원소가 음수인 경우를 처리해야 한다.

 

풀이

def solution(A):
    max_ending = max_slice = A[0]

    for i in range(1, len(A)):
        max_ending = max(A[i], max_ending + A[i])
        max_slice = max(max_ending, max_slice)
    
    return max_slice

 

max_ending과 max_slice를 명확히 하고 넘어가야 이 간단한 코드를 이해할 수 있다.

• max_ending: 현재 인덱스까지의 부분 배열 중에서 가장 큰 합
• max_slice: 현재까지 찾은 모든 부분 배열 중에서 가장 큰 합

좀 더 설명해 보자면,

max_ending은 반복문을 실행하는 각 단계에서, 현재 부분 배열(지금 배열이 최선이라고 가정하고 계산 중인)의 최대 합을 계산한다.

max_slice은 모든 max_ending을 비교하여(실제로는 모든 값을 나열하고 비교하지 않는다. 하지만 모든 max_ending은 max_slice에 게 도전하게 된다.) 최대 합을 계산한다.

 

한 줄씩 이해해 보자.

 

`max_ending = max_slice = A[0]`

초기화 하는 부분이다.

배열의 첫 번째 원소로 초기화 한다.

0으로 초기화를 하면, 모든 원소가 음수인 경우 0을 반환하는 문제가 생긴다.

 

`for i in range(1, len(A)):`

첫 번째 원소로 초기화 했으니, 첫 번째 원소는 건너뛴다.

 

`max_ending = max(A[i], max_ending + A[i])`

가장 고민을 많이 한 부분이다.

max_ending을 갱신할 때 무엇과 비교해야 하는가?

 

max() 함수의 두 번째 인자는 현재 부분 배열에 새로운 값을 더한 것이다. 자연스럽다.

첫 번째 인자는 A[i], 현재 항이다.

즉 현재 진행 중인 부분 배열 vs 새로 시작하는 것 중에서 비교하는 것이다.

 

`max_slice = max(max_ending, max_slice)`

현재 진행 중인 부분 배열이, 현재까지 최대 합인 max_slice에 도전하는 부분이다.

현재 진행 중인 것이 더 크면 왕위를 계승한다.

직관적이다.

 

후기

Maximum slice 유형을 O(N)에 풀이할 수 있는 뼈대 코드이다.

그래서 좀 깊게 분석해봤다.