likes
comments
collection
share

[剑指Offer-42] 连续子数组的最大和

作者站长头像
站长
· 阅读数 3

发布与个人公众号，打开微信，搜索MelodyJerry即可 [剑指Offer-42] 连续子数组的最大和

剑指 Offer 42. 连续子数组的最大和

LeetCode官方的难度定位为简单，个人觉得可以达到中等的！！！

难度简单通过率60.29%(182,636/302,898)

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为 O(n)O(n)O(n) 。

示例1:

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

提示：

  • 1 <= arr.length <= 10510^5105
  • -100 <= arr[i] <= 100

题解

① 动态规划

  • 值得注意的是题目描述中是连续，所以这里直接用动态规划就可以AC了。

  • 状态转移方程：

    • dp[i] = max(dp[i-1] + nums[i], nums[i])
      • dp[i]： 以nums[i]结尾的子数组的和的最大值
    • 为什么是dp[i-1]+nums[i]？
      • 思考dp[i-1]是否会对nums[i]带来负增益
      • 若带来负增益，自然是nums[i]值比dp[i-1]+nums[i]值更大
    • 初始条件：dp[0] = nums[0]

[剑指Offer-42] 连续子数组的最大和

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] = max(dp[i-1] + nums[i], nums[i])
             *  dp[i]: 以nums[i]为右区间的子数组的和的最大值
             */
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            /* 等价于
            if (dp[i - 1] >= 0) 
                dp[i] = dp[i - 1] + nums[i];
            else 
                dp[i] = nums[i];
            */
            max = Math.max(max, dp[i]); //更新max
        }
        return max;
    }
}

时间复杂度：O(n)O(n)O(n)

空间复杂度：O(n)O(n)O(n)

② 优化后的动态规划

这个优化主要是减少了空间复杂度

在上面的状态转移方程中提到：

  • 为什么是dp[i-1]+nums[i]？
    • 思考dp[i-1]是否会对nums[i]带来负增益，若带来负增益，自然是nums[i]值比dp[i-1]+nums[i]值更大

再看看代码中的这段注释：

/* 等价于
if (dp[i - 1] >= 0) 
    dp[i] = dp[i - 1] + nums[i];
else 
    dp[i] = nums[i];
*/

关键就是这里了，这里就很好地解释了那个思考：

  • 思考 dp[i-1]是否会对nums[i]带来负增益 ？

因此根据这段代码，可以对上面的动态规划做个小优化，

  • 关键在于sum>=0这个判断
    • 当sum<0时候，对当前的新整数num一定会造成负增益
      • 即sum+num一定<了num
      • 所以最大子数组的和一定不会再继续加当前整数
class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE; // 这是个注意点
        int sum = 0;
        for (int num : nums) {
            if (sum >= 0) 
                sum += num;
            else 
                sum = num;
            max = Math.max(max, sum); //更新max
        }
        return max;
    }
}

时间复杂度：O(n)O(n)O(n)

空间复杂度：O(1)O(1)O(1)

另一个版本的优化，其实也差不多的，容易理解。

该算法更为简便之处是忽略了对子序列的寻找比较，而是根据规律直接找出最佳答案。

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

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = 0 , thisSum = 0;
        for( int i = 0; i < nums.length ; i++ ){
            thisSum += nums[i];
            if(thisSum > maxSum)
                maxSum = thisSum;
            else if(thisSum < 0)
                thisSum = 0;
        }
        return maxSum;
    }
}

③ 分治法

  • 其实就是它的最大子序和要么在左半边，要么在右半边，要么是在中间。
  • 对于左、右边的序列，情况也是一样，因此可以用递归处理。
    • 递归的基本边界：左、右为相同位置的元素，即只有一个元素.
  • 中间部分的则可以直接计算出来。

以下是LeetCode官方题解的分治算法：

来源：最大子序和 - LeetCode官方题解- 方法二：分治

class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }
}

时间复杂度：O(n)O(n)O(n)

空间复杂度：O(log n)O(log\,n)O(logn)

建议阅读一下李威威同学的经典动态规划问题（理解「无后效性」）