解题思路:先把数组存起来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语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:481 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:745 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:615 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:604 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1162 |
简单的a+b (C语言代码)浏览:528 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:472 |
printf基础练习2 (C语言代码)浏览:618 |
大家好,我是验题君浏览:577 |
杨辉三角 (C语言代码)浏览:484 |