CSES 2. Maximum Subarray Sum II (1644)

출처: https://cses.fi/problemset/task/1644

---

문제 설명

Given an array of n integers, your task is to find the maximum sum of values in a contiguous subarray with length between a and b.

입력 

The first input line has three integers n, a and b: the size of the array and the minimum and maximum subarray length.

The second line has n integers x_1,x_2,…,x_n: the array values.

출력 

Print one integer: the maximum subarray sum.

입력 예

8 1 2
-1 3 -2 5 3 -5 2 2

출력 예

8

제약조건

• 1 <= n <= 2x10^5
• 1 <= a <= b<= n
• −10^9 <= x_i <= 10^9

---

문제 풀이 내용

입력을 받으면서, prefix sum을 계산한다. 특정한 구간 array[a] ~ array[b]의 합은 presum[b+1] - presum[a]를 통해서 구할 수 있다. subarray 길이에 따라서 값을 계산하도록 한다. 처음 알고리즘에서는 길이의 차가 5000이 넘어가면 제한시간에 걸렸다.

알고리즘 수정

prefix sum을 이용해서 읽어 들이면서, prefix sum의 위치가 a 보다 크면 multiset 에 prefix sum 값을 입력하고, 위치가 b 보다 커지면, 그 값들은 multiset에서 제외 시킨다. 부분합을 관리하는 방법은 queue, deque, priority queue 를 사용할 수도 있다.

프로그램 내용

...
    vector <long long> num_array(nNum);
    long long sum_array[nNum+1] = {0};

    long long num_max= -1e18;
    long long best = -1e18, sum = -1e18;

    sum_array[0] = 0;

    for (int idx = 0; idx < nNum; ++idx)
        cin >> num_array[idx];
        sum_array[idx+1] = num_array[idx] + sum_array[idx];
        num_max = max(num_max, num_array[idx]);

... /// N^2 
	for (int width=minW; width<= maxW; ++width)
        if (width == 1)
            best = num_max;
        else
            int left=0, right= width;
            long long tsum=sum;
            for (int idx = 0; idx <= nNum - width ; ++idx)
                tsum = sum_array[right] - sum_array[left];
                sum = max(sum, tsum);
                left++;
                right++;

            best = max(best, sum);
...

 

 수정한 프로그램

...
    maxW++; /// boundary

    vector <long long> num_array(nNum+1, 0);

    multiset <long long> sum_set;

    long long best = -1e18;

    for (int idx = 1; idx <= nNum; ++idx)
        cin >> num_array[idx];
        num_array[idx] += num_array[idx-1]; /// pre-sum update

        if ( idx - minW >= 0) /// window check
            sum_set.insert(num_array[idx-minW]);

        if ( idx - maxW >= 0) /// window check - too big
            sum_set.erase(sum_set.find(num_array[idx-maxW]));

        if ( sum_set.size()) /// check maximum
            best = max(best, num_array[idx]-*sum_set.begin());
...

 

 

Sorting and Searching ( link )