来源:力扣 (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 贪心算法
算法:
- 遍历数组,使用 sum 变量计算每一个节点时的最大和,用 ans 表示当前所有区间的最大子序和。
- 运行到第 i 个节点的时候,如果
sum > 0
,说明对当前节点有增益效果,sum 继续加上当前节点。 - 如果
sum <= 0
,说明之前的序列对当前节点来说没有增益效果,之前的和可以舍弃。 sum 从当前节点开始重新计算。 - 然后比较 ans 和 sum 的大小,较大的赋值给 sum 。
图例:
图片来源于解答:画解算法:53. 最大子序和 , © 著作权归作者所有 。
以数组 [-2, 3, -1, 1, -3] 为例,初始化时设置 sum 为 0,ans 为第一个元素的值:
访问第一个元素-2,当前 sum 为 0,更新 sum 为当前节点的值-2,sum 和 ans 对比 ans 还是-2:
访问第二个元素 3,因为 sum = -2
,如果加上当前节点,会使得连续和变成 1(还不如不加,不加是 3) 。因此重新计算 sum,设置 sum 为当前节点值 3,继续往前计算:
访问第三个元素-1,此时 sum > 0
,对-1 有增益效果,sum 加上-1 等于 2,ans 不变:
第四个元素:
到第五个元素时,sum = 3
,加上-3 之后等于 0,ans 依旧等于 3:
然后到此结束,最大连续和是 3 。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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; } }; |
复杂度分析:
- 时间复杂度:O(n)
- 空间复杂度:O(1)
2.2 动态规划
算法:
其实动态规划的思路和上面的贪心算法差不多,关键的结果是动态规划的状态方程:假设 dp[i] 是第 i 个节点时候的最大连续和,那怎么计算它的值呢?
其实还是和上面的贪心算法一样,只要 dp[i - 1] 加上当前节点的和大于当前节点,那么 dp[i] 就等于和值。否则 dp[i] 就应该设置为当前节点值,所以它的状态转移方程是:
1 2 |
dp[0] = nums[0]; dp[i] = max(dp[i - 1] + nums[i], nums[i]) |
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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) 。
评论