来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/maximum-subarray/

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

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

示例:

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

进阶:

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

分治法并不能算是最优解,但是可以锻炼对该算法的掌握情况。本题不考虑此算法。

二、题解

2.1 贪心算法

算法:

  1. 遍历数组,使用sum变量计算每一个节点时的最大和,用ans表示当前所有区间的最大子序和。
  2. 运行到第i个节点的时候,如果sum > 0,说明对当前节点有增益效果,sum继续加上当前节点。
  3. 如果sum <= 0,说明之前的序列对当前节点来说没有增益效果,之前的和可以舍弃。sum从当前节点开始重新计算。
  4. 然后比较ans和sum的大小,较大的赋值给sum。

图例:

图片来源于解答:画解算法:53. 最大子序和 , © 著作权归作者所有 。

以数组[-2, 3, -1, 1, -3]为例,初始化时设置sum为0,ans为第一个元素的值:

访问第一个元素-2,当前sum为0,更新sum为当前节点的值-2,sum和ans对比ans还是-2:

image2781361f9b1cc7d6.png

访问第二个元素3,因为sum = -2,如果加上当前节点,会使得连续和变成1(还不如不加,不加是3)。因此重新计算sum,设置sum为当前节点值3,继续往前计算:

imagefd03c8e73879b133.png

访问第三个元素-1,此时sum > 0,对-1有增益效果,sum加上-1等于2,ans不变:

image1f06514c3fa63f36.png

第四个元素:

image8742e9aae039ff80.png

到第五个元素时,sum = 3,加上-3之后等于0,ans依旧等于3:

imagedaf7eae811ef6e59.png

然后到此结束,最大连续和是3。

代码:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans, sum, i;
        ans = nums.size() > 0 ? nums[0] : 0;

        for (i = 0, sum = 0; i < nums.size(); i++) {
            if (sum <= 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }

            ans = max(ans, sum);
        }
        return ans;
    }
};

image.png

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

2.2 动态规划

算法:

其实动态规划的思路和上面的贪心算法差不多,关键的结果是动态规划的状态方程:假设dp[i]是第i个节点时候的最大连续和,那怎么计算它的值呢?

其实还是和上面的贪心算法一样,只要dp[i - 1]加上当前节点的和大于当前节点,那么dp[i]就等于和值。否则dp[i]就应该设置为当前节点值,所以它的状态转移方程是:

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

代码:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int i, sum;
        vector<int> dp(nums.size());

        if (nums.size() == 0) {
            return 0;
        }

        dp[0] = nums[0];
        sum = dp[0];

        for (i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            sum = max(dp[i], sum);
        }

        return sum;
    }
};

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n),整个状态中只用到了dp[i]和dp[i - 1],优化成O(1)。
最后修改:2019 年 12 月 06 日
喜欢就给我点赞吧