求子數組的最大和

分析：輸入一個整形數組，數組裡有正數也有負數，數組中一個或連續的多個正數，求所有子數組的和的最大值。

當我們加上一個正數時，和會增加；當我們加上一個負數時，和會減少。如果目前得到的和是個負數，那麼這個和在接下來的累加中應該抛棄并重新清零，不然的話這個負數将會減少接下來的和。

是以需采用DP思想，記錄下目前元素之和（為其最優狀态，既最大），将其與目前所得的最大和比較，若大于則更新，否則繼續。狀态的累加遵循這個過程：如果目前和小于0，則放棄該狀态，将其歸零。

本文轉自夏雪冬日部落格園部落格，原文連結：http://www.cnblogs.com/heyonggang/p/3196553.html，如需轉載請自行聯系原作者