C++党，前缀和数组处理

解题思路:先把数组存起来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）级别