最大子序和

来源Leetcode第53题最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

这题上课讲过，思路是分治，分越过中点，没有越过中点，又分中点左边，中点右边，共3种情况。
不过写的时候忘记了，于是先采用了万能的循环遍历，在倒数第三个测试用例时TLE了，打扰了

普通解法

用O(n^2)的时间，即2个循环去遍历所有子序列的情况，最终保存最大值即可，方法简单，但是会超时。
坑在于max值的设置，要设置成Integer.MIN_VALUE，以及第2重循环，将上一个子序列的值保留下来。
但是这样的效率非常低，用时62ms，击败了7.70%用户2333.

代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int max = Integer.MIN_VALUE ;
        if(len == 0) return 0;
        for(int i = 0 ; i < len ; i ++ ){
            int sum = nums[i];
            if(sum > max)
                max = sum ;
            for(int j = i + 1 ; j < len ;j++){
                sum += nums[j];
                if(sum > max)
                    max = sum;
            }
        }
        return max ;
    }
}

动态规划

思路

动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果

[动图(https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/)见
代码如下：

 public int maxSubArray(int[] nums) {
     int ans = nums[0];
     int sum = 0;
     for(int num: nums) {
         if(sum > 0) {
             sum += num;
         } else {
//这里包括了对sum 初始化为nums[0]
             sum = num;
         }
         ans = Math.max(ans, sum);
     }
     return ans;
 }

分治

思路见算法导论分治一节
数据结构与算法分析第二章P29
但是运行时间反而不如动态规划啊2333
代码来自：

  public int maxSubArray(int[] nums) {
      int len = nums.length;
      if (len == 0) {
          return 0;
      }
      return maxSubArraySum(nums, 0, len - 1);
  }

  private int maxCrossingSum(int[] nums, int left, int mid, int right) {
      // 一定会包含 nums[mid] 这个元素
      int sum = 0;
      int leftSum = Integer.MIN_VALUE;
      // 左半边包含 nums[mid] 元素，最多可以到什么地方
      // 走到最边界，看看最值是什么
      // 计算以 mid 结尾的最大的子数组的和
      for (int i = mid; i >= left; i--) {
          sum += nums[i];
          if (sum > leftSum) {
              leftSum = sum;
          }
      }
      sum = 0;
      int rightSum = Integer.MIN_VALUE;
      // 右半边不包含 nums[mid] 元素，最多可以到什么地方
      // 计算以 mid+1 开始的最大的子数组的和
      for (int i = mid + 1; i <= right; i++) {
          sum += nums[i];
          if (sum > rightSum) {
              rightSum = sum;
          }
      }
      return leftSum + rightSum;

  }

  private int maxSubArraySum(int[] nums, int left, int right) {
      if (left == right) {
          return nums[left];
      }
      int mid = (left + right) >>> 1;
      return max3(maxSubArraySum(nums, left, mid),
              maxSubArraySum(nums, mid + 1, right),
              maxCrossingSum(nums, left, mid, right));
//返回左边最大或右边最大，或者跨越中点
  }

  private int max3(int num1, int num2, int num3) {
      return Math.max(num1, Math.max(num2, num3));
  }