Pagini recente » Cod sursa (job #2498147) | Cod sursa (job #3260474) | Cod sursa (job #1458333) | Cod sursa (job #1836519) | Cod sursa (job #3145971)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
const int MAX_LENGTH = 50000;
const int MAX_SUM = 1250000000;
int main() {
int numsLen, minLen;
fin >> numsLen >> minLen;
int nums[MAX_LENGTH + 1], sums[MAX_LENGTH + 1], st = 1, maxLen = 0, maxSt = 0, maxEnd = 0, maxSum = -MAX_SUM - 1;
for (int i = 1; i <= numsLen; ++i) {
fin >> nums[i];
if (sums[i - 1] + nums[i] > nums[i]) {
sums[i] = sums[i - 1] + nums[i];
} else {
sums[i] = nums[i];
st = i;
}
if (i - st + 1 >= minLen && i - st + 1 > maxLen && sums[i] > maxSum) {
maxSum = sums[i];
maxSt = st;
maxEnd = i;
maxLen = i - st + 1;
}
}
if (maxLen < minLen) {
int sum = 0;
for (int i = 1; i <= numsLen; ++i) {
sum += nums[i];
if (i > minLen) {
sum -= nums[i - minLen];
}
if (sum > maxSum && i >= minLen) {
maxSum = sum;
maxSt = i - minLen + 1;
maxEnd = i;
}
}
}
fout << maxSt << ' ' << maxEnd << ' ' << maxSum;
return 0;
}
/*
8 3
0 -6 2 1 4 -1 3 -5
=>
3 7 9
8 3
1 2 3 -1 -1 1 2 3
=>
1 8 10
8 3
1 2 3 -5 -5 1 2 3
=>
1 3 6
3 3
-1 -2 -3
=>
1 3 -6
4 3
-1 -2 -3 1
=>
2 4 -4
4 2
-5 5 -5 5
=>
1 2 0
*/