题目描述

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

样例

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

算法1

(贪心) $O(n)$

class Solution {
    public int maxSubArray(int[] nums) {
        //解法一，贪心
        int sum = 0, max = nums[0];
        for(int i: nums){
            if(sum>0){
                sum += i;
            }else{
                sum = i;
            }
            max = Math.max(sum, max);
        }
        return max;
    }
}

参考文献

https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/

算法2

(动态规划) $O(n)$

 public int maxSubArray(int[] nums) {
        //解法二，动态规划
        int sum = 0, max = nums[0];
        for(int i: nums){
            sum = Math.max(sum+i, i);
            max = Math.max(sum, max);
        }
        return max;
    }

参考文献

https://leetcode-cn.com/problems/maximum-subarray/solution/zheng-li-yi-xia-kan-de-dong-de-da-an-by-lizhiqiang/

算法3

(分治) $O(nlogn)$

   public int maxSubArray(int[] nums) {
        //解法三，动态规划
        return divArray(nums, 0, nums.length-1);
    }
    private int divArray(int[] nums, int i, int j){
        if(i == j)
            return nums[i];

        int center = (j+i)/2;

        int left = divArray(nums, i, center);
        int right = divArray(nums, center+1, j);

        int leftsum = 0;
        int leftmax = nums[center];
        for(int a=center; a>=i; a--){
            leftsum = leftsum+nums[a];
            leftmax = Math.max(leftsum, leftmax);
        }

        int rightsum = 0;
        int rightmax = nums[center+1];
        for(int a=center+1; a<=j; a++){
            rightsum = rightsum+nums[a];
            rightmax = Math.max(rightmax,rightsum);
        }

        int mid = leftmax+rightmax;

        return Math.max(mid,Math.max(left,right));

    }
}

参考文献

https://leetcode-cn.com/problems/maximum-subarray/solution/zheng-li-yi-xia-kan-de-dong-de-da-an-by-lizhiqiang/