原题链接：疯狂的裁缝
解题思路:先把数组存起来q[n]，然后求前缀和数组S，S[i]代表从第一个到第i个的所有元素和，即1~i的价值，S[r]-S[l-1]即为区间l~r的价值和
~
注意事项:前缀和数组一般从下标1开始，时间复杂度为o（n^2），可以通过q[i]的正负来减少遍历次数，因为最大的价值的起始段一定是从第一个不为负价值开始的
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #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）级别
9.9 分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复