劍指 Offer 42. 連續(xù)子數組的最大和

題意：輸入一個整型數組，數組中的一個或連續(xù)多個整數組成一個子數組。求所有子數組的和的最大值。
要求時間復雜度為O(n)。

解題思路

解法：
最簡單的解法肯定是雙層for循環(huán)，遞歸去找最大的子數組和，但是我們也知道，這個必定會超時的。仔細推導題目，發(fā)現這個好像是一個DP問題，是否可以找到狀態(tài)轉移方程呢？
1.我們定義，F(n)為以nums[n]數字結尾的子數組的，最大和，不難推導出F(n)與F(n-1)關系

當F(n-1)<=0時，F(n)=nums[n]
當F(n-1)> 0時，F(n)=nums[n] + F(n-1)
2.,F(n) = max(F(n-1)+nums[n],nums[n])

解題遇到的問題

無

后續(xù)需要總結學習的知識點

無

##解法1
class Solution {
    public int maxSubArray(int[] nums) {
        // DP,F(n) = max(F(n-1)+nums[n],nums[n])
        // 我們定義，F(n)為以nums[n]數字結尾的子數組的，最大和，不難推導出F(n)與F(n-1)關系
        int pre = 0, max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            max = Math.max(max, pre);
        }
        return max;
    }
}