最大子序和(Maximum suborder sum)

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

示例 1:

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

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

提示:

1 <= nums.length <= 105
-104 <= nums[i] <= 104

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

解法一:动态规划+贪心思想

首先要明白以下几点:

  • 设置dp[i]为第i位的暂存值(注意:不是最大值,只是下标滑到第i位时,dp的数值)
  • 最大子序和的第一位一定为 正数,
  • 如果一个序列全为负数,那么就要求负数的最大值(不要想当然的觉得最大数大于0!然后就随随便便的把dp[i]=0),
  • 如果dp[i-1]<=0,那么就要勇敢舍弃前面算的,从当前位重新开始(违反第2条)。
  • 如果dp[i-1]>0,当然要加上当前位(贪心),至于加上当前位后是会减少dp[i]或者增加,留给下一个循环去判断。

代码如下:

class Solution {
    public int maxSubArray(int[] nums) {

        int [] dp = new int [nums.length];
        dp[0] = nums[0];

        for(int i=1;i<nums.length;i++){
            if(dp[i-1]<=0){
                dp[i] = nums[i];
            }
            else{
                dp[i] = dp[i-1]+nums[i];
            }
        }
        java.util.Arrays.sort(dp);
        return dp[nums.length-1];
    }
}

上述代码并没有清楚的写出动态规划的统一方程,但由for循环中的两个if,

    if(dp[i-1]<=0){
        dp[i] = nums[i];
    }
    else{
        dp[i] = dp[i-1]+nums[i];
    }

可以推测dp公式:

dp[i] = nums[i]+Math.max(dp[i-1], 0)

故上述代码可简化为:

class Solution {
    public int maxSubArray(int[] nums) {

        int [] dp = new int [nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for(int i=1;i<nums.length;i++){
            dp[i] = nums[i] + Math.max(dp[i-1], 0);
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

继续优化

class Solution {
    public int maxSubArray(int[] nums) {
        int temp_i = nums[0];
        int max = nums[0];
        for(int i=1;i<nums.length;i++){
            temp_i = nums[i] + Math.max(temp_i, 0);
            max = Math.max(temp_i, max);
        } 
        return max;
    }
}
————————

Give you an integer array nums. Please find a continuous sub array with the maximum sum (the sub array contains at least one element) and return its maximum sum.

A subarray is a contiguous part of an array.

Example 1:

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

Example 2:

输入:nums = [1]
输出:1

Example 3:

输入:nums = [5,4,-1,7,8]
输出:23

Tips:

1 <= nums.length <= 105
-104 <= nums[i] <= 104

Advanced: if you have implemented a solution with complexity O (n), try using a more sophisticated divide and conquer method.

Solution 1: dynamic programming + greedy thought

First, understand the following points:

  • Set DP [i] as the temporary value of bit I (Note: it is not the maximum value, but the value of DP when the subscript slides to bit I)
  • The first bit of the maximum suborder sum must be a positive number,
  • If a sequence is all negative numbers, the maximum value of negative numbers is required (do not assume that the maximum number is greater than 0! And then casually set DP [i] = 0),
  • If DP [I-1] < = 0, you should bravely abandon the previous calculation and start again from the current bit (in violation of Article 2).
  • If DP [I-1] > 0, of course, add the current bit (greedy). Adding the current bit will reduce DP [i] or increase, leaving it to the next cycle to judge.

The code is as follows:

class Solution {
    public int maxSubArray(int[] nums) {

        int [] dp = new int [nums.length];
        dp[0] = nums[0];

        for(int i=1;i<nums.length;i++){
            if(dp[i-1]<=0){
                dp[i] = nums[i];
            }
            else{
                dp[i] = dp[i-1]+nums[i];
            }
        }
        java.util.Arrays.sort(dp);
        return dp[nums.length-1];
    }
}

The above code does not clearly write the unified equation of dynamic programming, but it is composed of two if in the for loop,

    if(dp[i-1]<=0){
        dp[i] = nums[i];
    }
    else{
        dp[i] = dp[i-1]+nums[i];
    }

It can be inferred that DP formula:

dp[i] = nums[i]+Math.max(dp[i-1], 0)

Therefore, the above code can be simplified as:

class Solution {
    public int maxSubArray(int[] nums) {

        int [] dp = new int [nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for(int i=1;i<nums.length;i++){
            dp[i] = nums[i] + Math.max(dp[i-1], 0);
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

Continue to optimize

class Solution {
    public int maxSubArray(int[] nums) {
        int temp_i = nums[0];
        int max = nums[0];
        for(int i=1;i<nums.length;i++){
            temp_i = nums[i] + Math.max(temp_i, 0);
            max = Math.max(temp_i, max);
        } 
        return max;
    }
}