출처: 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 )
'CSES' 카테고리의 다른 글
| CSES 3. Dice Combinations (1633) (0) | 2019.10.09 |
|---|---|
| CSES 8. Minimal Rotation (1110) (0) | 2019.10.09 |
| CSES 2. Movie Festival II (1632) (0) | 2019.10.07 |
| CSES 2. Subarray Sums I (1660) (0) | 2019.10.03 |
| CSES 2. Nearest Smaller Values (1645) (0) | 2019.10.03 |