番禺建设银行网站,wordpress 密码失败,怎样上传wordpress,wordpress ishopping顾得泉#xff1a;个人主页
个人专栏#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂#xff0c;年薪百万#xff01; 一、最大子数组和
题目链接#xff1a;最大子数组和
题目描述 给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连…
顾得泉个人主页
个人专栏《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂年薪百万 一、最大子数组和
题目链接最大子数组和
题目描述 给你一个整数数组 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 nums.length 105-104 nums[i] 104
解法
1.状态表示: 对于线性dp我们可以用「经验题目要求」来定义状态表示: i.以某个位置为结尾巴拉巴拉; ii.以某个位置为起点巴拉巴拉。 这里我们选择比较常用的方式以「某个位置为结尾」
结合「题目要求」定义一个状态表示: dp[i]表示:以i位置元素为结尾的「所有子数组」中和的最大和
2.状态转移方程: dp[i]的所有可能可以分为以下两种 i.子数组的长度为1:此时dpLi nums[i]; ii.子数组的长度大于1:此时 dp[i]应该等于以i - 1做结尾的「所有子数组」中和的最大值再加上nums[i]也就是dp[i - 1] nums[i] 由于我们要的是最大值,因此应该是两种情况下的最大值因此可得转移方程: dp[i] max (nums[i]dp[i - 1] nums[i])
3.初始化: 可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点: i.辅助结点里面的值要「保证后续填表是正确的」; ii.「下标的映射关系」 在本题中最前面加上一个格子并且让dp[0] 即可
4.填表顺序: 根据「状态转移方程」易得填表顺序为「从左往右」
5.返回值: 状态表示为「以1为结尾的所有子数组」的最大值但是最大子数组和的结尾我们是不确定的。因此我们需要返回整个dp表中的最大值
代码实现
class Solution {
public:int maxSubArray(vectorint nums) {int n nums.size();vectorint dp(n 1);int ret INT_MIN;for(int i 1; i n; i){dp[i] max(nums[i - 1], dp[i - 1] nums[i - 1]);ret max(ret, dp[i]);}return ret;}
}; 二、环形子数组的最大和
题目链接环形子数组的最大和
题目描述 给定一个长度为 n 的环形整数数组 nums 返回 nums 的非空 子数组 的最大可能和 环形数组 意味着数组的末端将会与开头相连呈环状。形式上 nums[i] 的下一个元素是 nums[(i 1) % n] nums[i] 的前一个元素是 nums[(i - 1 n) % n] 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上对于子数组 nums[i], nums[i 1], ..., nums[j] 不存在 i k1, k2 j 其中 k1 % n k2 % n
示例 1
输入nums [1,-2,3,-2]
输出3
解释从子数组 [3] 得到最大和 3示例 2
输入nums [5,-3,5]
输出10
解释从子数组 [5,5] 得到最大和 5 5 10示例 3
输入nums [3,-2,2,-3]
输出3
解释从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3提示
n nums.length1 n 3 * 104-3 * 104 nums[i] 3 * 104
解法 本题与「最大子数组和」的区别在于考虑问题的时候不仅要分析「数组内的连续区域」还要考虑「数组首尾相连」的一部分。结果的可能情况分为以下两种: i.结果在数组的内部包括整个数组; ii.结果在数组首尾相连的一部分上 其中对于第一种情况我们仅需按照「最大子数组和」的求法就可以得到结果记为 fmax。对于第二种情况我们可以分析一下: i.如果数组首尾相连的一部分是最大的数组和那么数组中间就会空出来一部分; ii.因为数组的总和sum是不变的那么中间连续的一部分的和一定是最小的;因此我们就可以得出一个结论对于第二种情况的最大和应该等于sum - gmin 其中,gmin表示数组内的「最小子数组和」 两种情况下的最大值就是我们要的结果 但是由于数组内有可能全部都是负数第一种情况下的结果是数组内的最大值(是个负数)第二种情况下的 gmin sum求的得结果就会是0。若直接求两者的最大值就会是0。但是实际的结果应该是数组内的最大值。对于这种情况我们需要特殊判断一下 由于「最大子数组和」的方法已经讲过这里只提一下「最小子数组和」的求解过程其实与「最大子数组和」的求法是一致的。用f表示最大和g表示最小和
1.状态表示: g[i]表示:以i做结尾的所有子数组中和的最小值
2.状态转移方程: g[i]的所有可能可以分为以下两种: i.子数组的长度为1 :此时g[i] nums[i] ; ii.子数组的长度大于1∶此时 g[i应该等于以i - 1做结尾的「所有子数组」中和的最小值再加上nums[i]也就是g[i - 1] nums[i] 由于我们要的是最小子数组和因此应该是两种情况下的最小值因此可得转移方程: g[i] min( nums[i]g[i - 1] nums[i])
3.初始化: 可以在最前面加上一个辅助结点帮助我们初始化。使用这种技巧要注意两个点: i.辅助结点里面的值要保证后续填表是正确的; ii.下标的映射关系 在本题中最前面加上一个格子并且让g[0] 0即可
4.填表顺序:
根据状态转移方程易得填表顺序为「从左往右」
5.返回值: a.先找到f表里面的最大值-fmax ; b.找到g表里面的最小值- gmin ; c.统计所有元素的和-sum ; d.返回sum gmin ? fmax : max ( fmax, sum - gmin)
代码实现
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int n nums.size();vectorint f(n 1), g(n 1);int fmax INT_MIN, gmin INT_MAX, sum 0;for(int i 1; i n; i){int x nums[i - 1];f[i] max(x, x f[i - 1]);fmax max(fmax, f[i]);g[i] min(x, x g[i - 1]);gmin min(gmin, g[i]);sum x;}return sum gmin ? fmax : max(fmax, sum - gmin);}
}; 三、乘积最大子数组
题目链接乘积最大子数组
题目描述 给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积 测试用例的答案是一个 32-位 整数 子数组 是数组的连续子序列
示例 1:
输入: nums [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6示例 2:
输入: nums [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组提示:
1 nums.length 2 * 104-10 nums[i] 10nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
解法 这道题与「最大子数组和」非常相似我们可以效仿着定义一下状态表示以及状态转移: i. dp[i]表示以i为结尾的所有子数组的最大乘积 ii. dp[i] max ( nums[i]dp[i - 1]* nums[i]); 由于正负号的存在我们很容易就可以得到这样求dp[i的值是不正确的。因为 dp[i -1]的信息并不能让我们得到dp[i]的正确值。比如数组[-25-2]用上述状态转移得到的dp数组为[-25-2]最大乘积为5。但是实际上的最大乘积应该是所有数相乘结果为20 究其原因就是因为我们在求dp[2]的时候因为nums[2]是一个负数因此我们需要的是「 i - 1位置结尾的最小的乘积(-10)」这样一个负数乘以「最小值」才会得到真实的最大值。因此我们不仅需要一个「乘积最大值的dp表」还需要一个「乘积最小值的dp表」
1状态表示: f[i]表示:以i结尾的所有子数组的最大乘积 g[i]表示:以i结尾的所有子数组的最小乘积
2状态转移方程: 遍历每一个位置的时候我们要同步更新两个dp数组的值。 对于f[i]也就是「以为结尾的所有子数组的最大乘积」对于所有子数组可以分为下面三种形式: i.子数组的长度为1也就是nums[i] ; ii.子数组的长度大于1但nums[i] 0此时需要的是i - 1为结尾的所有子数组的最大乘积f[i - 1]再乘上nums[i]也就是nums[i] * f[i - 1]; ili.子数组的长度大于1但nums[i]0此时需要的是i - 1为结尾的所有子数组的最小乘积g[i - 1]再乘上nums[i]也就是nums[i] * g[i - 1];(如果nums[i] 0所有子数组的乘积均为0三种情况其实都包含了) 综上所述f[i] max(nums[i]max(nums[i] * f[i - 1]nums[i] * g[i -1]))。 对于g[i]也就是「以1为结尾的所有子数组的最小乘积」对于所有子数组可以分为下面三种形式: i.子数组的长度为1也就是nums[i]; ii.子数组的长度大于1)但nums[i] 0此时需要的是i – 1为结尾的所有子数组的最小乘积g[i - 1]再乘上nums[i]也就是nums[i] * g[i - 1]; iii.子数组的长度大于1但nums[i] 0此时需要的是i - 1为结尾的所有子数组的最大乘积f[i - 1]再乘上nums[i]也就是nums[i] * f[i - 1]; 综上所述g[i] min(nums[i]min(nums[i] * f[i - 1]nums[i] * g[i -1])) (如果nums[i] 0所有子数组的乘积均为0三种情况其实都包含了
3.初始化: 可以在最前面加上一个辅助结点帮助我们初始化。使用这种技巧要注意两个点: i.辅助结点里面的值要保证后续填表是正确的; ii.下标的映射关系。 在本题中最前面加上一个格子并且让f[o]g[o]1即可
4.填表顺序: 根据状态转移方程易得填表顺序为从左往右两个表一起填
5.返回值: 返回f表中的最大值
代码实现
class Solution {
public:int maxProduct(vectorint nums) {int n nums.size();vectorint f(n 1), g(n 1);f[0] g[0] 1;int ret INT_MIN;for(int i 1; i n; i){int x nums[i - 1], y f[i - 1] * nums[i - 1], z g[i - 1] * nums[i - 1];f[i] max(x, max(y, z));g[i] min(x, min(y, z));ret max(ret, f[i]);}return ret;}
}; 结语今日的刷题分享到这里就结束了希望本篇文章的分享会对大家的学习带来些许帮助如果大家有什么问题欢迎大家在评论区留言~~~
