给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。
要求算法的时间复杂度为O(n)。
输入有两行：
第一行是n值（1<=n<=10000)；
第二行是n个整数。
输出最大子段和。
在这里给出一组输入。例如：
6
-2 11 -4 13 -5 -2
在这里给出相应的输出。例如：
20
给出一组数字，求最大字段和
时间复杂度：用了三个for循环，但是不是叠加在一起的，所以时间复杂度是o(n);
空间复杂度：空间复杂度是o(1)
对于这道题的算法，我和搭档想了很久，隐隐约约有头绪但是不知道怎么下手。我觉得应该把正数提取出来，因为这个最大字段和的第一个数字和最后一个数字一定是正数，亦或者就一个正数。我把正数的下标提取出来，然后根据连续的逻辑，将正数之间的搭配组合的规律找出，比如有n个正数，那么正数之间的搭配有（n-1）*n/2个组合，这个组合的意思是例如从第一个正数开始，一直加到第二个正数；第2个正数一直加到第n个正数；并在这些组合里找到最大的和就是最大字段和。这个想法可以找到最大字段和，但是确有段错误。我和搭档想了很久，这虽然不是最好的答案，但理论上并没有错。后来，在一个同学的启发下，我设一个变量max，从第一个正数加起，每加一次就和max比较一起，如果和比max大，就把和赋值给max，如果和小于零，就把和置为0，继续加到最后一个正数为止。其实这个方法不需要知道正数的位置，但是我觉得如果在一个庞大的数组里，特别是这个数组的开始和结尾充满了很多负数的时候，正数的下标找出来，可以在一定程度上减少运算量。
原文：https://www.cnblogs.com/xxnjwz-9/p/11710590.html