注册一个网站域名一年需要多少钱,人人做网站,连云港建设公司网站,一个具体网站的seo优化方案1. 题目链接#xff1a;1567. 乘积为正数的最长子数组长度
2. 题目描述#xff1a; 给你一个整数数组 nums #xff0c;请你求出乘积为正数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。 请你返回乘积为正数的最长子数组长度。 示…1. 题目链接1567. 乘积为正数的最长子数组长度
2. 题目描述 给你一个整数数组 nums 请你求出乘积为正数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。 请你返回乘积为正数的最长子数组长度。 示例 1 输入nums [1,-2,-3,4]
输出4
解释数组本身乘积就是正数值为 24 。示例 2 输入nums [0,1,-2,-3,-4]
输出3
解释最长乘积为正数的子数组为 [1,-2,-3] 乘积为 6 。
注意我们不能把 0 也包括到子数组中因为这样乘积为 0 不是正数。示例 3 输入nums [-1,-2,-3,0,1]
输出2
解释乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。提示 1 nums.length 10^5-10^9 nums[i] 10^9 3. 解法动态规划
3.1 算法思路
1. 状态表示
f[i]表示以i结尾的所有子数组中乘积为正数的最长子数组的长度
g[i]表示以i结尾的所有子数组中乘积为负数的最长子数组的长度
2. 状态转移方程 3. 初始化
可以在最前面加上一个辅助结点帮助我们完成初始化使用这种技巧要注意两个点
辅助结点里面的值要保证后续填表是正确的下标的映射关系
在本题中最起码加上一个格子并且让 f[0]g[0]0即可‘ 4. 填表顺序
根据状态转移方程填表顺序为从左往右两个表一块填
5. 返回值:
根据状态表示我们要返回f表中的最大值
3.2 C算法代码
class Solution {
public:int getMaxLen(vectorint nums) {int n nums.size(); // 获取数组长度vectorint f(n 1), g(n 1); // 初始化两个辅助数组f和g长度为n1int ret INT_MIN; // 初始化结果变量ret为最小整数for (int i 1; i n; i) {if (nums[i - 1] 0) { // 如果当前元素大于0f[i] f[i - 1] 1; // 更新f数组的当前元素为前一个元素加1g[i] g[i - 1] 0 ? 0 : g[i - 1] 1; // 更新g数组的当前元素为前一个元素加1如果前一个元素为0则保持不变} else if (nums[i - 1] 0) { // 如果当前元素小于0f[i] g[i - 1] 0 ? 0 : g[i - 1] 1; // 更新f数组的当前元素为前一个元素加1如果前一个元素为0则保持不变g[i] f[i - 1] 1; // 更新g数组的当前元素为前一个元素加1}ret max(ret, f[i]); // 更新结果变量ret为f数组中的最大值}return ret; // 返回结果变量ret}
};
