题目：
问题描述:
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。也就是是说找出一段连续的子序列，该序列的和是最大的，输出该最大值。
算法描述：
用一个一维数组记录下每个以该数字为结尾的最大子段和，若该为负数则置为零。
max[i]=max[i-1]+a[i]
if（max[i]<0）max[i] = 0;
算法时间及空间复杂度分析:
时间复杂度为 O（n） 该算法总共进行了n-1次相加与n次比较，每次比较与相加的时间复杂度为O（1）
空间复杂度为O（n） 该算法用了一个长度为n的一维数组来记录数据
心得体会：个人觉得在做动态规划的题目时，要逻辑清晰，想好要用一维还是二维的数组来存放数据，以及想清每个存放的数据之间的关系，写出表达式
原文：https://www.cnblogs.com/halo1234/p/9942475.html