原题链接在这里：

题目：

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.

题解：

采用的是DP解法. 把原有问题拆成小问题. maxSubArray(int [] nums, int i). 表示到 [0,i]段最大的sub array. 前提是包括 i 元素.

maxSubArray(nums, i) = nums[i] + maxSubArray(nums, i-1) > 0 ? maxSubArray(nums, i-1) : 0.

同时维护全局最大值.

历史信息就是local[i-1] 和 global[i-1], 更新当前信息时先更新局部最优.

local[i] = Math.max(local[i-1]+nums[i], nums[i]), 有可能local[i-1]是负数，就直接取nums[i], 然后更新全局最优.

global[i] = Math.max(lcoal[i], global[i-1]), 要么是原来的全局最优，要么是局部最优，此时能涵盖所有解。如果全局最优不包含当前值，那么会被维护在global[i-1]中，若包含当前值，那么就是local[i].

Note: local, global的初始化是nums[0]. 不能初始化成0, 然后从i=1开始，比如[-1], Output:0, Expected:-1, 这种corner case 就会出错.

Time Complexity: O(n).n = nums.length.

Space: O(1).

AC Java:

1 public class Solution { 2     public int maxSubArray(int[] nums) { 3         if(nums == null || nums.length ==0){ 4             return 0; 5         } 6         int global = nums[0]; 7         int local = nums[0]; 8         for(int i = 1; i< nums.length; i++){ 9             local = Math.max(local + nums[i], nums[i]);10             global = Math.max(global, local);11         }12         return global;13     }14 }

类似, , .

跟上.

Reference: