最大连续子段和/区间最大和

题目描述：给出一个长为n的数列，a1，a2，……，an，求和最大的连续子序列，即找到一对（i，j），i<=j，使ai+ai+1+……+aj的和最大，输出这个和

思路：先求出前n项的前缀和，再用a[j] - a[i] ,求出从 i 到 j 的子段和，动态更新，求出最大子段和

#include
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <=n; i++ )
	    scanf("%d", &a[i]);
	int ans = 0;int minn = -N;
	for(int i = 1; i <= n; i++)
	{
		a[i] += a[i - 1];
	}

	for ( int i = 1 ; i <= n ; i++ )
	{
    ans = max(ans,a[i]-minn);
    minn = min(minn,a[i]);
	}
	
	printf("%d", ans);
	return 0;
}