求长度为k的子序列的最大值，为什么我的代码不对，感觉没问题

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. #define int long long
   
4. signed main()
   
5. {
   
6.     int n,k;
   
7.     cin>>n>>k;
   
8.     queue<int>q;
   
9.     int sum=0,res=-1e9;
   
10.     for(int i=1;i<=n;i++)
    
11.     {
    
12.         int x;
    
13.         cin>>x;
    
14.         q.push(x);
    
15.         if(q.size()==k)
    
16.         {
    
17.             while(k--)
    
18.             {
    
19.                 sum+=q.front();     
    
20.             }
    
21.             q.pop();
    
22.         }
    
23.         if(sum>res)
    
24.         {
    
25.             res=sum;
    
26.         }
    
27.     }
    
28.     cout<<res<<endl;
    
29. }
    
30. // 1 2 3 4
    
31. // 1  2  3  

复制代码

FishC

你的代码中有一处逻辑错误：在计算子序列和sum时，没有将sum重新置为0。因此，每次计算的都是整个序列的和，而不是长度为k的子序列的和。

以下是修正后的代码：

1. #include <iostream>
   
2. #include <queue>
   
3. using namespace std;
   
4. 
   
5. #define int long long
   
6. 
   
7. signed main()
   
8. {
   
9.     int n, k;
   
10.     cin >> n >> k;
    
11.     queue<int> q;
    
12.     int sum = 0, res = -1e9;
    
13.     for (int i = 1; i <= n; i++)
    
14.     {
    
15.         int x;
    
16.         cin >> x;
    
17.         q.push(x);
    
18.         sum += x;
    
19.         if (q.size() > k)
    
20.         {
    
21.             sum -= q.front();
    
22.             q.pop();
    
23.         }
    
24.         if (q.size() == k && sum > res)
    
25.         {
    
26.             res = sum;
    
27.         }
    
28.     }
    
29.     cout << res << endl;
    
30.     return 0;
    
31. }

复制代码

修正后的代码中，在每次循环中，先将当前元素x加入sum中，然后判断队列q的大小是否大于k。如果大于k，则需要将队首元素从sum中减去，并将其从队列中弹出。这样可以保证sum始终表示长度为k的子序列的和。最后，如果sum大于之前记录的最大值res，则更新res的值。

希望对你有所帮助！如果你还有其他问题，请随时提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

zhangjinxuan

你只会对于 q.front 的元素进行统计，没有统计 q 所有的元素，还有你这个 k-- 直接就把 k 的值改变了。可以考虑使用支持随机访问的容器，例如 deque。

再注意一下 deque 与 queue 的区别，以及 sum 的清空就可以了：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. #define int long long
   
4. signed main()
   
5. {
   
6.     int n,k;
   
7.     cin>>n>>k;
   
8.     deque<int>q;
   
9.     int sum=0,res=-1e9;
   
10.     for(int i=1;i<=n;i++)
    
11.     {
    
12.         int x;
    
13.         cin>>x;
    
14.         q.push_back(x);
    
15.         if(q.size()==k)
    
16.         {
    
17.                 sum = 0;
    
18.             for(int i=0;i<k;++i)
    
19.             {
    
20.                                 sum+=q[i];
    
21.                         }
    
22.             q.pop_front();
    
23.                         if(sum>res)
    
24.                         {
    
25.                             res=sum;
    
26.                         }
    
27.         }
    
28.     }
    
29.     cout<<res<<endl;
    
30. }

复制代码

请注意代码的时间复杂度是 O(nk) 的，如果无法通过本题可以使用一个变量 sum 维护 q 中所有的元素，减少了大部分不必要的访问与求和操作。

如果无法通过，可以使用以下代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. #define int long long
   
4. signed main()
   
5. {
   
6.     int n,k;
   
7.     cin>>n>>k;
   
8.     int a[n+1];
   
9.     int sum=0,res=-1e18;
   
10.     for(int i=1;i<=n;i++)
    
11.     {
    
12.         cin>>a[i];
    
13.         sum+=a[i];
    
14.         if(i>=k)
    
15.         {
    
16.                         if(sum>res)
    
17.                         {
    
18.                             res=sum;
    
19.                         }
    
20.                         sum-=a[i-k+1];
    
21.         }
    
22.     }
    
23.     cout<<res<<endl;
    
24. }

复制代码