描述
对n个整数的序列a1,a2,a3,....an, 元素ai, ai+1,ai+2, ....... aj-1,aj称为其一个子序列。其中 1 <= i <= j <= n。子序列元素之和称为子段和，即， ai + ai+1+ ai+2 +.......+ aj-1+ aj .
现在，给你一个整数序列（n <= 100000)，请求出其所有子串和中最大的一个的值。保证所有子段和都可以用long表示。
输入
第一行是一个整数n，表示序列中整数的个数。
第二行包含n个整数，即a1,a2,a3,....,an
输出
一个整数，为所有子段和中最大的一个的值。
样例输入
6
-2 11 -4 13 -5 -2
样例输出
20
#include<stdio.h> #include<algorithm> #include<iostream> using namespace std; int main() { int a[100000],n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } int dp[n]; dp[0]=a[0]; int answer=dp[0]; for(int i=1;i<n;i++) { dp[i]=max(dp[i-1]+a[i],a[i]); answer=max(answer,dp[i]); } printf("%d",answer); return 0; }
