【算法】-求一个数组的最大连续数组的值

题目要求：这道题是最近面试某个互联网公司的时候遇到的。题目大概是：给定一个数组A[]={1,-5,-3,2,7,-8,4},求其中连续的几个数的最大的和是多少。

最开始的思路，是从第一个数开始，计算第一个数为开始位置到最后一个数过程中所有的子数组的和，然后在计算第二个数为开始位置到最后一个数过程中所有的子数组的和，……，直到计算最后一个数的和。这个过程一个嵌套的for循环语句就可以了。

因为这个方法的时间复杂度为O（N^2）,不是很理想，还有一种更省时的方法。

更省时的思路：利用DP的思想，在对每次循环进行求和时，如果前面的部分对后面是“负贡献”的话，我们就应该”舍弃”前面的部分，从当前位置作为子数组开始的位置。这样，只需要遍历这个数组一次就可以，时间复杂度减小至O（N）