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

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

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

#includeusing 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;}