在线做海报网站,如何拿模板做网站,wordpress开发者中心,网站建设一般多少钱比较合适力扣53最大子数组和 题目动态规划贪心 题目
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组是数组中的一个连续部分。
示例 1#xff1a;
输入#xff1a;nums… 力扣53最大子数组和 题目动态规划贪心 题目
给你一个整数数组 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 定义dp数组的含义dp[i]为从以下标i结束的连续数组的最大和 2 接着推导出递推公式想要得到dp[i]有两种途径
第一个就是加上当前元素了即dp[i] dp[i - 1] nums[i] 第二个就是没有将当前元素加到序列中而是从当前元素开始新的子数组即dp[i] nums[i]
3 接下来分析一下初始化一维的dp数字全都初始化为0这是肯定的因为dp[i]一开始确实没有一个固定的值 第一个dp[i] dp[i - 1] nums[i]所以i要从1开始遍历不然会访问内存错误dp[0]需要单独初始化为nums[0]
class Solution {
public:int maxSubArray(vectorint nums) {int len nums.size();vectorint dp(len 1, 0);dp[0] nums[0];int result dp[0];for(int i 1; i len; i ){dp[i] max(dp[i - 1] nums[i], nums[i]);if(dp[i] result) result dp[i];}return result;}
};cpp
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;}
};贪心
贪心是从局部最优推导全局最优
那么这道题的局部最优在哪里呢
如果 -2 1 在一起计算起点的时候一定是从 1 开始计算因为负数只会拉低总和这就是局部最优的地方
所以思路关键在于当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”
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;}
};
