53. 最大子序和

发表于   |   分类于 LeetCode   |   本文已被浏览 858 次   |   暂无评论

题目描述

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

示例 1：

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

示例 2：

输入:nums = [1]
输出:1
示例:3：

提示：

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

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

解题思路

动态规划解题步骤：

  1. 确定状态
  2. 找到转移方程
  3. 确定初始以及边界条件
  4. 计算结果

看起来很简单，但是就是死活无法找到转移方程。没办法，只能去评论区偷一手。得到转移方程 dp[i]=num[i]+max(dp[i-1],0); 接下来就水到渠成了，边界条件就是dp[0] = nums[0] 作为初始值开始循环计算统计最大dp[i] 即可。

代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
    for (int i = 1; i < nums.length; i++) {
        dp[i]= Math.max(0,dp[i-1])+nums[i];
        if (max< dp[i]){
            max = dp[i];
        }
    }
    return max;
    }
}

运行结果

22:32    info
                        解答成功:
                        执行耗时:1 ms,击败了94.82% 的Java用户
                        内存消耗:38 MB,击败了98.78% 的Java用户

题解

方法一：动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：分治

这个分治方法类似于「线段树求解最长公共上升子序列问题」的 pushUp 操作。 也许读者还没有接触过线段树，没有关系，方法二的内容假设你没有任何线段树的基础。当然，如果读者有兴趣的话，推荐阅读线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」，还是非常有趣的。

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);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

小结

找规律，提高找转移方程的能力，面试可不能去评论区偷😂

属性值
URLhttps://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn3cg3/
Bloghttps://www.leey.eu.org/2021/03/22/53-%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
Notionhttps://www.notion.so/04564e3bc5174b6fbd4ef1c74cbc6b13
标签分治算法, 动态规划, 数组, 简单
创建时间Mar 21, 2021 9:44 PM
添加新评论