题目描述

给定一个整数数组，找到一个连续子数组其元素之和最大并返回
Input：nums
Output：最大连续子数组之和

三种解法，分别是动态规划、贪心法、分治法，其中分治算法不是最优的。

1. 动态规划

定义 $dp\left[i\right]$dp[i]：以位置 $i$i为结尾的子数组最大和
$dp[i+1]=\{\begin{array}{c}dp\left[i\right]+nums\left[i\right],dp\left[i\right]>0\\ nums\left[i\right],其他\end{array}$dp[i+1]={dp[i]+nums[i],dp[i]>0nums[i],其他​
  需要遍历数组一次，时间复杂度为O(n)，空间复杂度为O(1)。缺点是直接在nums上操作，会改变原来的数组nums。

	/** * 动态规划 * @param nums * @return */
    public int maxSubArrayDynamic(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int maxSum = nums[0];
        for(int i = 1;i<nums.length;i++){
            nums[i] += nums[i-1] > 0 ? nums[i-1] : 0;
            maxSum = Math.max(maxSum, nums[i]);
        }
        return maxSum;
    }

2. 贪心法

  curSum用于记录当前和（每一步都选择最优的方案）
  仅仅需要遍历数组一次，时间复杂度为O(n)，空间复杂度为O(1)。

	/** * 贪心 * @param nums * @return */
    public int maxSubArrayGreed(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int curSum = nums[0], maxSum = curSum;
        for(int i = 1;i<nums.length;i++){
            curSum = Math.max(curSum + nums[i], nums[i]);
            maxSum = Math.max(maxSum, curSum);
        }
        return maxSum;
    }	

3. 分治

  首先将数组划分成左和右两部分，具有最大和的连续子数组的位置可能有如下三种情况：

1. 位于左边的数组部分；
2. 位于右边的数组部分；
3. 位于左和右交叉的部分，即最大子数组有一部分在左边，一部分在右边。

其中，第一种情况和第二种情况可以递归。第三种情况由函数crossSum暴力计算，需要遍历数组一次，使得时间复杂度需要乘O(n)

    /** * 暴力计算包含位置p在内的最大子数组和 * @param nums * @param left * @param right * @param p * @return */
    private int crossSum(int[] nums, int left, int right, int p){
        if(left == right)   return nums[left];

        int leftSubsum = Integer.MIN_VALUE;
        int rightSubsum = Integer.MIN_VALUE;

        int curSum = 0;
        for(int i = p;i >= left;i--){
            curSum += nums[i];
            leftSubsum = Math.max(leftSubsum, curSum);
        }
        curSum = 0;
        for(int i = p+1;i<=right;i++){
            curSum += nums[i];
            rightSubsum = Math.max(rightSubsum, curSum);
        }
        return leftSubsum + rightSubsum;
    }
    private int helper(int[] nums, int left, int right){
        if(left == right) return nums[left];
        int p = (left + right) >>> 1;
        int leftSum = helper(nums, left, p);
        int rightSum = helper(nums, p+1, right);
        int crossSum = crossSum(nums, left, right, p);
        return Math.max(crossSum, Math.max(leftSum, rightSum));
    }
    /** * 分治 * @param nums * @return */
    public int maxSubArrayDivide(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        return helper(nums, 0, nums.length-1);
    }

时间复杂度为O(nlogn)，helper函数多次递归，造成了空间复杂度为O(logn)。