MaxSliceSum

🔗 문제 링크

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

❔ 문제 설명

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).

⚠️ 제한사항

• 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].

💡 풀이 (언어 : Python)

인덱스가 연결 되는 것 상관없이 전체 케이스인 줄 알았는데 연속된 인덱스의 수의 합으로 판단하는 문제였다. 풀이가 떠오르지 않아 타인의 정답을 공부했다. 다시 작성한 코드는 아래와 같다. 풀이의 아이디어는 처음부터 끝까지 for문을 돌지만 중간에 누적합이 음수로 떨어지면 뒤의 어떤 수가 나오던 누적합을 중단하고 다시 새로 0부터 누적합을 시작하는게 포인트였다. 시간복잡도는 $O(N)$

def solution(A):
    current = 0
    maximum = -1000000

    for a in A:
        # 누적합 계산
        nextSum = current + a
        # 최대 값보다 크면 최대값 갱신
        if nextSum > maximum:
            maximum = nextSum
        # 중간에 음수로 떨어지면 뒤에가 양수든 음수든 누적합 안하고 안더해주고 새로 시작(0으로)
        if nextSum > 0:
            current = nextSum
        else:
            current = 0

    return maximum