佛山市门户网站建设,wordpress电影列表页,济宁软件开发网站建设,废旧网站哪个做的最好53. 最大子数组和 - 力扣#xff08;LeetCode#xff09;
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组 是数组中的一个连续部分。
示例 1#xff1a;
输入…53. 最大子数组和 - 力扣LeetCode
给你一个整数数组 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若-2 和 1在一起累加计算起点一定从1开始因为负数只会拉低总和这就是贪心贪的地方
局部最优当前 “连续和” 为负数的时候立刻放弃从下一个元素重新计算 “连续和”因为负数加上下一个元素 “连续和” 只会越来越小。全局最优选取最大“连续和”
局部最优的情况下并记录最大的 “连续和” 可以推出全局最优 不断调整最大子序和区间的起始位置区间终止位置是不用调整的因为区间的终止位置在count取得最大值了及时记录下来了。这相当于是用result记录最大子序和区间和变相的算是调整了终止位置
if (count result) result count;C代码
class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0;for (int i 0; i nums.size(); i) {count nums[i];if (count result) { // 取区间累计的最大值相当于不断确定最大子序终止位置result count;}if (count 0) count 0; // 相当于重置最大子序起始位置因为遇到负数一定是拉低总和}return result;}
};
时间复杂度O(n)空间复杂度O(1) 二、动态规划
dp[i] : 表示包括 i 之前的最大连续子序列和 i 0dp[0] -2
i 1count (-2) 1 -1,在count 和 nums[1] 1中选取最大值即 dp[1] max(dp[0] nums[1],nums[1]); 所以dp[1] 1
i 2由于前面已经计算过包括i 1之前的最大连续子序列和并且将值保存在 dp[1] 里所以count dp[1] (-3) 1 (-3) -2接着在count 和 nums[2] -3中选取最大值即 dp[2] max(dp[1] nums[2],nums[2]);所以dp[2] -2表示包括i 2之前的最大连续子序列和。同理如下推导
i 3count dp[2] 4 2dp[3] max(2,4);所以dp[3] 4。发现 count nums[3]这时候取最大值就可以让dp[3] nums[3]表示接下来可以调整起点让 i 3 为起点
i 4count dp[3] (-1) 3dp[4] max(3,-1);所以dp[4] 3.发现count nums[4]的表示可以保持让 i 3为起点
i 5count dp[4] 2 5dp[5] max(5,2);所以dp[5] 5.发现count nums[5]的表示可以保持让 i 3为起点
i 6count dp[5] 1 6dp[6] max(6,1);所以dp[6] 6.发现count nums[6]的表示可以保持让 i 3为起点
i 7count dp[6] (-5) 1dp[7] max(1,-5);所以dp[7]1.发现count nums[7]的表示可以保持让 i 3为起点
i 8count dp[7] 4 5dp[8] max(5,4);所以dp[8] 5.发现count nums[8]的表示可以保持让 i 3为起点
① count dp[i-1] nums[i];② dp[i] max(count,nums[i]);↓↓↓↓
③ dp[i] max(dp[i-1] nums[i],dp[i]);
class Solution {
public:int maxSubArray(vectorint nums) {if (nums.size() 0) return 0;vectorint dp(nums.size(), 0); // dp[i]表示包括i之前的最大连续子序列和dp[0] nums[0];int result dp[0];for (int i 1; i nums.size(); i) {dp[i] max(dp[i - 1] nums[i], nums[i]); // 状态转移公式if (dp[i] result) result dp[i]; // result 保存dp[i]的最大值}return result;}
};
时间复杂度O(n)空间复杂度O(n)
优化空间复杂度
class Solution {
public:// 动态规划 优化空间复杂度int maxSubArray(vectorint nums) {if(nums.size() 0) return 0;int pre nums[0];int result nums[0];for(int i1; inums.size(); i) {pre max(pre nums[i],nums[i]); if(pre result) result pre;}return result;}
};
时间复杂度O(n)空间复杂度O(1)
参考和推荐文章、视频
代码随想录 (programmercarl.com)
贪心算法的巧妙需要慢慢体会LeetCode53. 最大子序和_哔哩哔哩_bilibili
来自代码随想录的课堂截图
