53. 最大子序和/面试题42. 连续子数组的最大和(简单)

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

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray

思路1：

对于含有正数的序列而言,最大子序列肯定是正数,所以头尾肯定都是正数.我们可以从第一个正数开始算起,每往后加一个数便更新一次和的最大值;当当前和成为负数时,则表明此前序列无法为后面提供最大子序列和,因此必须重新确定序列首项.

思路2：

分治法的策略一般分为三步：

  • 定义基本情况
  • 将大问题不断分解为小问题，递归的解决
  • 合并所有情况并获得解

针对于该题，如果将整个数组分为左右两部分，该题可以把需要求解的目标序列（最大和序列）分为三种基本情况

  • 目标序列都在左半边
  • 目标序列都在右半边
  • 目标序列左右横跨

代码1：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = nums[0];
        for(int num: nums){
            sum = sum>0?(sum+num):num;
            maxSum = Math.max(maxSum,sum);
        }
        return maxSum;
    }
}

代码3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSubArray(int[] num) {
        int length = num.length;
        int[] dp = new int[length];
        //边界条件
        dp[0] = num[0];
        int max = dp[0];
        for (int i = 1; i < length; i++) {
            //转移公式如果要计算前i+1个元素构成的连续子数组的最大和，也就是计算dp[i]，只需要判断dp[i-1]是大于0还是小于0。如果dp[i-1]大于0，就继续累加，dp[i]=dp[i-1]+num[i]
            dp[i] = Math.max(dp[i - 1], 0) + num[i];
            //记录最大值
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    //第一种方法，分治法
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;

        return helper(0,nums.length-1,nums);
    }

    public int helper(int left,int right,int nums[]){

        if(left > right)
            return Integer.MIN_VALUE;

        int mid = (left+right) >>> 1;
        
        //左边最大
        int leftMaxSum = helper(left,mid-1,nums);
        //右边最大
        int rightMaxSum = helper(mid+1,right,nums);

        //计算横跨左右的最大数值

        //横跨的左边部分
        int currentSum = 0,spanLeftMax=0;
        for(int i = mid-1; i >= left;i--){
            currentSum += nums[i];
            spanLeftMax = Math.max(spanLeftMax,currentSum);
        }

        //横跨的右边部分
        currentSum=0;
        int spanRightMax = 0;

        for(int i = mid+1; i <=right; i++){
            currentSum += nums[i];
            spanRightMax = Math.max(spanRightMax,currentSum);
        }

        return Math.max(spanRightMax+spanLeftMax+nums[mid],
                        Math.max(leftMaxSum,rightMaxSum));

    }
}

作者：pangzihao
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-lian-xu-he-by-pangzihao/