最大子序和

题目

思路

• 记录每添加一个新的元素的和，将它与新添加的元素比较大小，取其最大值就能确定前面最大的子序和

  代码

  ```java public int maxSubArray(int[] nums) {

    int len = nums.length;
    if (len == 0) return 0;
    int[] preSun = new int[len];
    preSun[0] = nums[0];
    int max = nums[0], min = nums[0];
    for (int i = 1; i < len; i++) {
        preSun[i] += (preSun[i - 1] + nums[i]);
        min = Math.min(min, preSun[i - 1]);
        max = Math.max(min < 0 ? preSun[i] - min : preSun[i], max);
    }
    return max;

  }

  //1.递归 int max; public int maxSubArray(int[] nums) {

    max = nums[0];
    recur(nums, nums.length - 1);
    return max;
  

  }

  public int recur(int[] nums, int i) {

    if (i == 0) return nums[0];
    int res = Math.max(recur(nums, i - 1) + nums[i], nums[i]);
    max = Math.max(max, res);
    return res;
  

  }

//2.动态规划
public int maxSubArray(int[] nums) {
    int pre = nums[0], max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        pre = Math.max(pre + nums[i], nums[i]);
        max = Math.max(max, pre);
    }
    return max;
}

``` 最大子序和