Lesson 9. Maximum slice problem - MaxSliceSum

1. 문제

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:
  int solution(vector<int> &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].

 

주어진 배열에서, 가장 큰 부분 합(P, Q)을 구하는 문제 \( (0 \leq P \leq Q < N) \)

\( (P, Q) = A[P] + A[P+1] + ... + A[Q] \)

 

 

예시) return 5

A[0]	A[1]	A[2]	A[3]	A[4]
3	2	-6	4	0

 

A[3] + A[4] = 4

A[2] + A[2] = -6

A[0] + A[1] = 5

 

2. 매개변수 제한

• Vector A 크기: 1 ~ 1,000,000
• Vector A 요소 값: -1,000,000 ~ 1,000,000
• 부분 합: -2,147,483,648 ~ 2,147,483,647

 

3. 코드 (C++)

MaxProfit 문제(MaxProfit #2)와 동일한 전략으로 문제를 풀면 된다.

요소 하나하나를 더해가면서 값을 누적시키고, 음수가 되면 누적 값을 초기화 한다.

단, 매개변수가 음수를 포함하므로, 변수 초기값 설정에 신경써야 한다.

#include <limits>

int solution(vector<int> &A) {

    int max = numeric_limits<int>::min();
    int sum = 0;
    for(size_t i = 0; i < A.size(); i++)
    {
        sum += A[i];
        if(sum > max) max = sum;
        if(sum < 0) sum = 0;
    }

    return max;
}