解题思路:先把数组存起来q[n],然后求前缀和数组S,S[i]代表从第一个到第i个的所有元素和,即1~i的价值,S[r]-S[l-1]即为区间l~r的价值和
~
注意事项:前缀和数组一般从下标1开始,时间复杂度为o(n^2),可以通过q[i]的正负来减少遍历次数,因为最大的价值的起始段一定是从第一个不为负价值开始的
参考代码:
#include<iostream> using namespace std; const int N=1e6+10; int q[N],S[N];//q是原始数据,S是前缀和数组 int main() { cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) cin>>q[i];//输入数据 for(int i=1;i<=n;i++) S[i]=S[i-1]+q[i];//前缀和数组的初始化 int m=-999999;//用来存储l~r区间的最大价值的 for(int i=1;i<=n;i++)//接下来直接遍历所有左右区间 i是区间左端点 j是区间右端点 { for(int j=i;j<=n;j++) { m=max(m,S[j]-S[i-1]);//每次将m更新为最大价值区间的和 while(q[i]<=0) i++;//记住!!一定要优化i,每次最大价值的开始是一定从大于0的价值开始的,否则会TLE(时间超限) } } cout<<m; return 0; }
前缀和能将求区间和的问题优化到o(1)级别
0.0分
1 人评分
大神老白 (C语言代码)浏览:640 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:697 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:818 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:1067 |
1128题解(返回值为数组的情况)浏览:453 |
简单的a+b (C语言代码)浏览:460 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:602 |
【计算球体积】 (C语言代码)浏览:1548 |
多组数据新方法浏览:355 |
【蟠桃记】 (C语言代码)浏览:628 |