题意是给一个长度为n的数组,求长度不超过m的子数组元素之和的最大值。
结果老是不对,希望大神们能指点指点,感激不尽!!!
我的想法是开一个队列,每次读入的时候sum就加上读入这个的值,如果这个sum小于0了就将读入的队列全部出队,每次用sum和ans比较,如果sum>ans,就更新ans的值,最后结果就是答案了,可是数据一大,结果就不对了。
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n, m;
int value[100010] = {0};
int MIN[100010] = { 0 };
int qianzhui[100010] = { 0 };
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
queue<long long>s;
long long sum = 0, ans = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> value[i];
if (*max_element(value + 1, value + 1 + n) <= 0)
{
cout << *max_element(value + 1, value + 1 + n);
return 0;
}
for (int i = 1; i <= n; i++)
{
if (s.size() < m)
{
s.push(value[i]);
sum += value[i];
if (sum < 0)
{
while (!s.empty())
s.pop();
sum = 0;
continue;
}
if (sum > ans)
ans = sum;
}
else
{
sum -= s.front();
s.pop();
s.push(value[i]);
sum += value[i];
if (sum < 0)
{
while (!s.empty())
s.pop();
sum = 0;
continue;
}
if (sum > ans)
ans = sum;
}
}
for (; !s.empty();)
{
sum -= s.front();
s.pop();
if (sum > ans)
ans = sum;
}
cout << ans;
}