題目要求：這道題是最近面試某個(gè)互聯(lián)網(wǎng)公司的時(shí)候遇到的。題目大概是：給定一個(gè)數(shù)組A[]={1,-5,-3,2,7,-8,4},求其中連續(xù)的幾個(gè)數(shù)的最大的和是多少。

最開(kāi)始的思路，是從第一個(gè)數(shù)開(kāi)始，計(jì)算第一個(gè)數(shù)為開(kāi)始位置到最后一個(gè)數(shù)過(guò)程中所有的子數(shù)組的和，然后在計(jì)算第二個(gè)數(shù)為開(kāi)始位置到最后一個(gè)數(shù)過(guò)程中所有的子數(shù)組的和，……，直到計(jì)算最后一個(gè)數(shù)的和。這個(gè)過(guò)程一個(gè)嵌套的for循環(huán)語(yǔ)句就可以了。

因?yàn)檫@個(gè)方法的時(shí)間復(fù)雜度為O（N^2）,不是很理想，還有一種更省時(shí)的方法。

更省時(shí)的思路：利用DP的思想，在對(duì)每次循環(huán)進(jìn)行求和時(shí)，如果前面的部分對(duì)后面是“負(fù)貢獻(xiàn)”的話，我們就應(yīng)該”舍棄”前面的部分，從當(dāng)前位置作為子數(shù)組開(kāi)始的位置。這樣，只需要遍歷這個(gè)數(shù)組一次就可以，時(shí)間復(fù)雜度減小至O（N）