https://www.51nod.com/Challenge/Problem.html#problemId=1049
解题思路：
既然是求最大子段和，第一要求它是连续的一段数，二是最大。题目要求这里强调如果数据全为负数时就输出零，简化了问题。
申请一个数组dp[N]，如果 dp[i-1]+a[i]<0 的话，就跳过a[i]这一项。对于这里我们想象一下，dp数组中的值一定是大于等于零的，当dp[i]=dp[i-1]+a[i]<0时，将数存入dp是没有意义的。数据为负时就直接跳过它找下一个为正的数进行判断。如果dp[i-1]>0，然后遇到了一个正整数，那么dp[i-1]+a[i]的值应是大于等于a[i]的左邻域内包含a[i]的任意连续数的和。即，如果dp[i-1]+a[i]为正的话，那么就继续遍历，期望将其变为最大值。
代码：
1 #include<math.h> 2 #include<ctype.h> 3 #include<stdio.h> 4 #include<string.h> 5 #include<limits.h> 6 7 #define N 100010 8 9 typedef long long int ll; 10 11 int main() 12 { 13 int n; 14 int a[N], dp[N]={0}; 15 int i, max; 16 max=INT_MIN; 17 scanf("%d", &n); 18 for(i=1; i<=n; i++){ 19 scanf("%d", &a[i]); 20 } 21 for(i=1; i<=n; i++){ 22 if(dp[i-1]+a[i]>0){ 23 dp[i]=dp[i-1]+a[i]; //到i为止的子段和 24 if(dp[i]>max) max=dp[i]; //如果dp[i]大于目前的最大值时，就更新max 25 } 26 } 27 28 printf("%d\n", max); 29 return 0; 30 }
原文：https://www.cnblogs.com/Arrokoth/p/12008418.html