给定n（1 <= n <= 100000）个整数（可能为负数）组成的序列a [1]，a [2]，a [3]，…，a [n]，求该序列如a [ I] + A [1 + 1] + ... + A [j]的的子段和的最大值。所当给的整数均为负数时定义子段为状语从句：0，依此定义，所求的最优值为：Max {0，a [i] + a [i + 1] + ... + a [j]}，1 <= i <= j <= n。例如，当（a [1]，a [2]， a [3]，a [4]，a [5]，a [6]）=（-2,11，-4,13，-5，-2）时，最大子段和为20。
注意：本变量要求用动态规划法替代，只需要输出最大子段和的值。
第一行输入整数n（1 <= n <= 100000），表示整数序列中的数据元素个数；
第二行依次输入n个整数，对应顺序表中存放的每个数据元素值。
输出所求的最大子段和
6 -2 11 -4 13 -5 -2
20
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <malloc.h> 4 int main() 5 { 6 int n,sum,max,i,a[100009]; 7 scanf("%d",&n); 8 sum=0;max=0; 9 for(i=0;i<=n-1;i++) 10 { 11 scanf("%d",&a[i]); 12 } 13 for(i=0;i<=n-1;i++) 14 { 15 sum+=a[i]; 16 if(sum<0) 17 { 18 sum=0; 19 } 20 if(sum>max) 21 { 22 max=sum; 23 } 24 } 25 printf("%d\n",max); 26 }
原文：https://www.cnblogs.com/xiaolitongxueyaoshangjin/p/12878230.html