关键词:
文章目录
LeetCode刷题笔记-动态规划-day6
152. 乘积最大子数组
1.题目
原题链接:152. 乘积最大子数组
2.解题思路
算法:动态规划 + 滚动数组优化
- f[i]表示所有从0到i并且选用a[i]获得的最大乘积
- g[i]表示所有从0到i并且选用a[i]获得的最小乘积
则有这样几种情况:
- 当a[i] >= 0时,f[i] = max(a[i], f[i - 1] * a[i])
- 当a[i] < 0时,f[i] = max(a[i], g[i - 1] * a[i])
- 当a[i] >= 0时,g[i] = min(a[i], g[i - 1] * a[i])
- 当a[i] < 0时,g[i] = min(a[i], f[i - 1] * a[i])
可以合并为:
- 当
a[i] >= 0
时f[i] = max(a[i], max(f[i-1] * a[i],g[i-1]*a[i]))
- 当
a[i]<0
时f[i] = max(a[i], max(g[i-1] * a[i],f[i-1]*a[i])
可以用滚动数组优化空间。详细见代码。
3.代码
class Solution
public:
int maxProduct(vector<int>& a)
int f=a[0],g=a[0];
int res=a[0];
for(int i=1;i<a.size();i++)
int t=a[i],fa=f*t,ga=g*t;
f=max(t,max(fa,ga));
g=min(t,min(fa,ga));
res=max(res,f);
return res;
;
1567. 乘积为正数的最长子数组长度
1.题目
原题链接:1567. 乘积为正数的最长子数组长度
2.解题思路
算法:动态规划
我们可以用两个数组f[i]
和g[i]
:
f[i]
表示以下标i结尾乘积为正数的最长子数组长度g[i]
表示以下标i结尾乘积为负数的最长子数组长度
这里我们可以得到递推公式:
- 如果当前数大于0,即
nums[i]>0
,之前的乘积乘以当前数,正负性是不会发生改变的,所以:f[i]=f[i-1]+1
- 如果
g[i-1]
不等于0的话,才加一,如果g[i-1]本身为0,这里为正数也不会改变
- 如果当前数小于0,即
nums[i]<0
,之前的乘积乘以当前数会改变乘积的正负性,所以:- 这时候
g[i]
应该等于f[i-1]+1
,因为f[i-1]
包含的数乘积是正数,乘以当前数刚好为负数。 f[i]
需要考虑g[i-1]
情况,如果g[i-1]
为0,这里f[i]
也还是为0,否则f[i]=g[i-1]+1
,负数乘负数为正数
- 这时候
- 如果当前数为0,即
nums[i]==0
,将f[i]
,g[i]
赋值为0 - 每次遍历维护最大值:
res=max(res,f[i]);
3.代码
class Solution
public:
int getMaxLen(vector<int>& nums)
int f=0,g=0;
if(nums[0]>0) f=1;
else if(nums[0]<0) g=1;
int res=f;
for(int i=1;i<nums.size();i++)
if(nums[i]>0)
f++;
g=(g==0)?0:g+1;
else if(nums[i]<0)
int t=f;
f=(g==0)?0:g+1;
g=t+1;
else
f=0,g=0;
res=max(res,f);
return res;
;
leetcode刷题笔记-动态规划-day7(代码片段)
文章目录LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目2.解题思路3.代码121.买卖股票的最佳时机1.题目2.解题思路3.代码122.买卖股票的最佳时机II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目原... 查看详情
leetcode刷题笔记-动态规划-day7(代码片段)
文章目录LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目2.解题思路3.代码121.买卖股票的最佳时机1.题目2.解题思路3.代码122.买卖股票的最佳时机II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目原... 查看详情
leetcode刷题笔记-动态规划-day1(代码片段)
文章目录LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目2.解题思路3.代码1137.第N个泰波那契数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目原题链接:509.斐波那契数2.解题思路可以用dp数组递推做... 查看详情
leetcode刷题笔记-动态规划-day1(代码片段)
文章目录LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目2.解题思路3.代码1137.第N个泰波那契数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目原题链接:509.斐波那契数2.解题思路可以用dp数组递推做... 查看详情
leetcode刷题笔记-动态规划-day5(代码片段)
文章目录LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目2.解题思路3.代码918.环形子数组的最大和1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目原题链接:53.最大子数组和2.解题思路算法:... 查看详情
leetcode刷题笔记-动态规划-day3(代码片段)
文章目录LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目2.解题思路3.代码213.打家劫舍II1.题目2.解题思路3.代码740.删除并获得点数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目原题链接:198.打家劫舍2.... 查看详情
leetcode刷题笔记-动态规划-day3(代码片段)
文章目录LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目2.解题思路3.代码213.打家劫舍II1.题目2.解题思路3.代码740.删除并获得点数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目原题链接:198.打家劫舍2.... 查看详情
leetcode刷题笔记-动态规划-day4(代码片段)
文章目录LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目2.解题思路3.代码45.跳跃游戏II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目原题链接:55.跳跃游戏2.解题思路算法:贪心我们用变量j表示从前... 查看详情
leetcode刷题笔记-动态规划-day4(代码片段)
文章目录LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目2.解题思路3.代码45.跳跃游戏II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目原题链接:55.跳跃游戏2.解题思路算法:贪心我们用变量j表示从前... 查看详情
leetcode刷题笔记-动态规划-day2(代码片段)
文章目录LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目2.解题思路3.代码746.使用最小花费爬楼梯1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目原题链接:70.爬楼梯2.解题思路算法:递推定义数组f[i]表示... 查看详情
leetcode刷题笔记-动态规划-day2(代码片段)
文章目录LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目2.解题思路3.代码746.使用最小花费爬楼梯1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目原题链接:70.爬楼梯2.解题思路算法:递推定义数组f[i]表示... 查看详情
leetcode刷题笔记——动态规划(代码片段)
动态规划的⼀般流程就是三步:暴⼒的递归解法->带备忘录的递归解法->迭代的动态规划解法。就思考流程来说,就分为⼀下⼏步:找到状态和选择->明确dp数组/函数的定义->寻找状态之间的关系。明确dp[i][j]... 查看详情
leetcode刷题笔记-数据结构-day6(代码片段)
文章目录LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述2.解题思路3.代码409.最长回文串1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述原题链接:415.字符串相加2.解题思路直接套用大... 查看详情
leetcode刷题笔记-动态规划-day1(代码片段)
文章目录LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目2.解题思路3.代码1137.第N个泰波那契数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目原题链接:509.斐波那契数2.解题思路可以用dp数组递推做... 查看详情
leetcode刷题分类笔记(代码片段)
leetcode刷题分类笔记202204130.常规操作1.链表83.删除排序链表中的重复元素203.移除链表元素2.二叉树leetcode108.将有序数组转换为二叉搜索树111.二叉树的最小深度113.路径总和II543.二叉树的直径3.动态规划45.跳跃游戏II96.不同的二叉搜... 查看详情
leetcode刷题笔记-动态规划-day5(代码片段)
文章目录LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目2.解题思路3.代码918.环形子数组的最大和1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目原题链接:53.最大子数组和2.解题思路算法:... 查看详情
leetcode刷题笔记-动态规划-day2(代码片段)
文章目录LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目2.解题思路3.代码746.使用最小花费爬楼梯1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目原题链接:70.爬楼梯2.解题思路算法:递推定义数组f[i]表示... 查看详情
leetcode刷题笔记-数据结构-day6(代码片段)
文章目录LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述2.解题思路3.代码409.最长回文串1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述原题链接:415.字符串相加2.解题思路直接套用大... 查看详情