呆~ 2019-04-29 22:15 采纳率: 100%
浏览 153
已采纳

acm初学,有点小问题希望大神指点指点

题意是给一个长度为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;
}
  • 写回答

1条回答 默认 最新

  • 呆~ 2019-04-29 22:38
    关注

    加大悬赏咯,开了个新问题https://ask.csdn.net/questions/759354

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 鸿业暖通修改详细负荷时闪退
  • ¥15 有偿求码,CNN+LSTM实现单通道脑电信号EEG的睡眠分期评估
  • ¥15 没有证书,nginx怎么反向代理到只能接受https的公网网站
  • ¥50 成都蓉城足球俱乐部小程序抢票
  • ¥15 yolov7训练自己的数据集
  • ¥15 esp8266与51单片机连接问题(标签-单片机|关键词-串口)(相关搜索:51单片机|单片机|测试代码)
  • ¥15 电力市场出清matlab yalmip kkt 双层优化问题
  • ¥30 ros小车路径规划实现不了,如何解决?(操作系统-ubuntu)
  • ¥20 matlab yalmip kkt 双层优化问题
  • ¥15 如何在3D高斯飞溅的渲染的场景中获得一个可控的旋转物体