博敏网站建设,大型网站 前端,wordpress分站点,深圳网站制作公司流程图算法沉淀——动态规划之子数组、子串系列 01.最大子数组和02.环形子数组的最大和03.乘积最大子数组04.乘积为正数的最长子数组长度 01.最大子数组和
题目链接#xff1a;https://leetcode.cn/problems/maximum-subarray/、
给你一个整数数组 nums #xff0c;请你找出一个具… 算法沉淀——动态规划之子数组、子串系列 01.最大子数组和02.环形子数组的最大和03.乘积最大子数组04.乘积为正数的最长子数组长度 01.最大子数组和
题目链接https://leetcode.cn/problems/maximum-subarray/、
给你一个整数数组 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
**进阶**如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。
思路
状态表示 使用「经验 题目要求」定义线性动态规划的状态表示。选择以「某个位置为结尾」的方式结合「题目要求」定义状态表示dp[i] 表示以 i 位置元素为结尾的「所有子数组」中和的最大和。 状态转移方程 将 dp[i] 的所有可能分为两种情况子数组的长度为 1 或子数组的长度大于 1。如果子数组长度为 1则 dp[i] nums[i]。如果子数组长度大于 1则 dp[i] 应该等于以 i-1 为结尾的「所有子数组」中和的最大值再加上 nums[i]即 dp[i-1] nums[i]。转移方程为 dp[i] max(nums[i], dp[i-1] nums[i])。 初始化 在最前面加上一个「辅助结点」用于初始化。辅助结点的值要保证后续填表是正确的因此设 dp[0] 0。辅助结点的存在需要注意下标的映射关系。 填表顺序 根据「状态转移方程」填表顺序为「从左往右」。 返回值 状态表 dp 表示以 i 为结尾的所有子数组的最大值但最大子数组和的结尾是不确定的。因此返回整个 dp 表中的最大值。
代码
class Solution {
public:int maxSubArray(vectorint nums) {int nnums.size();vectorint dp(n1);int retINT_MIN;for(int i1;in;i){dp[i]max(nums[i-1],dp[i-1]nums[i-1]);retmax(ret,dp[i]);}return ret;}
};02.环形子数组的最大和
题目链接https://leetcode.cn/problems/maximum-sum-circular-subarray/
给定一个长度为 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
思路
这个问题与「最大子数组和」的区别在于需要考虑数组首尾相连的情况。结果可能有两种情况一是在数组的内部包括整个数组二是在数组首尾相连的一部分上。
对于第一种情况按照「最大子数组和」的方法得到结果记为 fmax。对于第二种情况分析得出第二种情况的最大和应等于数组总和减去最小子数组和。其中最小子数组和表示为 gmin。两种情况下的最大值即为所求结果。然而需要特殊处理数组内全部为负数的情况因为直接比较两者的最大值可能会得到 0。这种情况下实际结果应为数组内的最大值。对于「最小子数组和」的求解过程与「最大子数组和」相同使用 f 表示最大和g 表示最小和。返回值先找到 f 表的最大值 fmax找到 g 表的最小值 gmin统计所有元素的和 sum返回 sum gmin ? fmax : max(fmax, sum - gmin)。
代码
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int nnums.size();vectorint f(n1);vectorint g(n1);int fmaxINT_MIN,gminINT_MAX,sum0;for(int i1;in;i){int xnums[i-1];sumx;f[i]max(x,xf[i-1]);fmaxmax(fmax,f[i]);g[i]min(x,xg[i-1]);gminmin(gmin,g[i]);}return sumgmin ? fmax : max(fmax,sum-gmin);}
};03.乘积最大子数组
题目链接https://leetcode.cn/problems/maximum-product-subarray/
给你一个整数数组 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-位 整数
思路
这道题类似于「最大子数组和」但需要考虑乘积而非和。定义两个状态数组 f[i] 和 g[i] 分别表示以 i 为结尾的所有子数组的最大乘积和最小乘积。
状态表示 f[i] 表示以 i 为结尾的所有子数组的最大乘积。g[i] 表示以 i 为结尾的所有子数组的最小乘积。 状态转移方程 对于 f[i]需要考虑三种情况子数组长度为 1子数组长度大于 1 且 nums[i] 0子数组长度大于 1 且 nums[i] 0。综上f[i] max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i - 1]))。对于 g[i]同样考虑三种情况。综上g[i] min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i - 1]))。 初始化 在最前面加上一个辅助结点并设置 f[0] g[0] 1。 填表顺序 从左往右两个表一起填。 返回值 返回 f 表中的最大值。
代码
class Solution {
public:int maxProduct(vectorint nums) {int nnums.size();vectorint f(n1);vectorint g(n1);f[0]g[0]1;int retINT_MIN;for(int i1;in;i){int xnums[i-1],yf[i-1]*nums[i-1],zg[i-1]*nums[i-1];f[i]max(x,max(y,z));g[i]min(x,min(y,z));retmax(ret,f[i]);}return ret;}
};04.乘积为正数的最长子数组长度
题目链接https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/
定一个整数数组nums找到其中所有元素的乘积为正的子数组的最大长度。
数组的子数组是从该数组中取出的零个或多个值的连续序列。
返回具有正积的子数组的最大长度。
示例1
输入 nums [1,-2,-3,4]
输出 4
解释数组 nums 的乘积已经为 24。示例2
输入 nums [0,1,-2,-3,-4]
输出 3
解释具有正积的最长子数组是 [1,-2,-3]其积为 6。
请注意我们不能在子数组中包含 0因为这会使乘积为 0而 0 不是正数。示例3
输入 nums [-1,-2,-3,0,1]
输出 2
解释具有正积的最长子数组是 [-1,-2] 或 [-2,-3]。限制条件
1 nums.length 105-109 nums[i] 109
思路
1. 状态表达 定义两个动态规划数组 f 和 g其中
f[i] 表示以 i 为结尾的所有子数组中乘积为正数的最长子数组长度。g[i] 表示以 i 为结尾的所有子数组中乘积为负数的最长子数组长度。
2. 状态转移方程 对于 f[i]根据当前元素 nums[i] 的值分三种情况讨论 如果 nums[i] 0说明当前子数组的乘积为零所以 f[i] 0。 如果 nums[i] 0说明当前子数组的乘积为正数直接找到 f[i - 1] 的值并加一即 f[i] f[i - 1] 1。 如果 nums[i] 0需要根据 g[i - 1]的值来判断 如果 g[i - 1] 为零表示以 i - 1 为结尾的最长负数子数组不存在所以 f[i] 0。如果 g[i - 1] 不为零表示以 i - 1 为结尾的最长负数子数组存在此时 f[i] g[i - 1] 1。
对于 g[i]也分三种情况讨论 如果 nums[i] 0说明当前子数组的乘积为零所以 g[i] 0。 如果 nums[i] 0说明当前子数组的乘积为负数直接找到 f[i - 1] 的值并加一即 g[i] f[i - 1] 1。 如果 nums[i] 0需要根据 g[i - 1]的值来判断 如果 g[i - 1] 为零表示以 i - 1 为结尾的最长负数子数组不存在所以 g[i] 0。如果 g[i - 1] 不为零表示以 i - 1 为结尾的最长负数子数组存在此时 g[i] g[i - 1] 1。
3. 初始化 在数组最前面加上一个辅助结点设置 f[0] g[0] 0。
4. 填表顺序 从左往右遍历数组同时填充 f 和 g 两个动态规划数组。
5. 返回值 返回 f 数组中的最大值即为最终结果。
代码
class Solution {
public:int getMaxLen(vectorint nums) {int nnums.size();vectorint f(n1);vectorint g(n1);int retINT_MIN;for(int i1;in;i){if(nums[i-1]0){f[i]f[i-1]1;g[i]g[i-1]0?0:g[i-1]1;}else if(nums[i-1]0){f[i]g[i-1]0?0:g[i-1]1;g[i]f[i-1]1;}retmax(ret,f[i]);}return ret;}
};
