動態規劃，前綴和，維護狀態更新。

題目

從題可以看出，找的是最大和的連續子數組，即一個數組中的其中一個連續部分。從前往后遍歷，每遍歷到一個數可以嘗試做疊加，注意是嘗試，因為有可能會遇到一個很大的負數，把前面加起來的都抵消掉，顯然不是所要的，因此在dp中需要一個做結果集的維護，與更新后的總數做比較，看看是否需要做更新。

class Solution {public int maxSubArray(int[] nums) {int[] f = new int[nums.length];f[0] = nums[0];int ans = f[0];for (int i = 1; i < nums.length; i++) {f[i] = Math.max(f[i - 1], 0) + nums[i];ans = Math.max(ans, f[i]);}return ans;}
}

然后這里用類似滾動數組的思想做優化，可以少用一個數組做空間復雜度上的優化。

class Solution {public int maxSubArray(int[] nums) {int ans = Integer.MIN_VALUE; int f = 0;for (int x : nums) {f = Math.max(f+ x, x) ;ans = Math.max(ans, f);}return ans;}
}

這題還可以用前綴和實現，子數組的元素和等于兩個前綴和的差，可以一邊遍歷數組計算前綴和，一邊維護前綴和的最小值。由于題目要求子數組不能為空，應當先計算前綴和減去最小前綴和，再更新最小前綴和。?

時間復雜度：O(n)，空間復雜度：O(1)。

class Solution {public int maxSubArray(int[] nums) {int ans = Integer.MIN_VALUE;int minPreSum = 0;int preSum = 0;for (int x : nums) {preSum += x; ans = Math.max(ans, preSum - minPreSum); minPreSum = Math.min(minPreSum, preSum); }return ans;}
}

動態規劃要找準狀態轉移方程及所需更新的狀態。

?