15.7最长递增子序列(中等)
题目描述:leetcode链接 300. 最长递增子序列
给你一个整数数组
nums
,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,
[3,6,2,7]
是数组[0,3,1,6,2,2,7]
的子序列
。示例 1:
输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。示例 2:
输入:nums = [0,1,0,3,2,3] 输出:4示例 3:
输入:nums = [7,7,7,7,7,7,7] 输出:1
思路:
1.dp[i]表示以nums[i]结尾的最长递增子序列的长度,其长度最小为1,因此对dp全部初始化为1
2.当nums[i] > nums[j]时,dp[i] = dp[j] + 1
当nums[i] <= nums[j]时,dp[i]则不变
因此,对于j∈[0 , i )遍历,dp[i] = max (dp[i] , dp[j] + 1)
3.返回dp中最大的值
举例说明:
无
代码:
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();int ans = 1;vector<int> dp(n, 1);for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if(dp[i] > ans) ans = dp[i];}return ans;}
};
15.8乘积最大子数组(中等)
题目描述:leetcode链接 152. 乘积最大子数组
给你一个整数数组
nums
,请你找出数组中乘积最大的非空连续 子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4] 输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
思路:
1.由于nums中存在负数,因此用两个vector存储以nums[i]结尾的乘积的最大值和最小值
2.初始化f_max[0] = f_min[0] = nums[0]
3.状态转移方程
f_max[i] = max(max(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i])
f_min[i] = min(min(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i])
4.返回f_max的最大值即可
举例说明:
无
代码:
class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();vector<int> f_min(n), f_max(n);f_max[0] = f_min[0] = nums[0];int ans = f_max[0];for (int i = 1; i < n; i++) {f_max[i] = max(max(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i]);f_min[i] = min(min(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i]);ans = max(f_max[i], ans);}return ans;}
};
15.9 分割等和子集(中等)
题目描述:leetcode链接 416. 分割等和子集
给你一个 只包含正整数 的 非空 数组
nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。示例 1:
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。示例 2:
输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
思路:
1.nums中的所有元素相加为sum,若sum为奇数,则直接返回false
2.令target=sum/2,dp[j]表示nums的子集中的元素之和是否可以等于j
vector<bool> dp(target + 1, false)
初始化dp[0] = true
3.对于nums[i]
dp[j] = dp[j] || dp[j - nums[i]],其中j∈[ nums[i], target ]
4.返回dp[target]
举例说明:
无
代码:
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i];}if(sum % 2 == 1) return false;int target = sum / 2;vector<bool> dp(target + 1, false);dp[0] = true;for(int i = 0; i < nums.size(); i++){for(int j = target; j >= nums[i]; j--){dp[j] = dp[j] || dp[j - nums[i]];}}return dp[target];}
};
15.10最长有效括号(困难)
题目描述:leetcode链接 32. 最长有效括号
给你一个只包含
'('
和')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。示例 1:
输入:s = "(()" 输出:2 解释:最长有效括号子串是 "()"示例 2:
输入:s = ")()())" 输出:4 解释:最长有效括号子串是 "()()"示例 3:
输入:s = "" 输出:0
思路:
1.dp[i]表示以s[i]结尾的最长有效括号数量
2.当s[i]==')',s[i - 1]=='('时,dp[i]=dp[i - 2] + 2;
当s[i]==')',s[i - 1]==')'时,如果s[i - 1 - dp[i - 1]]=='(',dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]
3.返回dp中的最大值
举例说明:
无
代码:
class Solution {
public:int longestValidParentheses(string s) {//1.当s[i]==')',s[i - 1]=='('时//dp[i]=dp[i - 2] + 2;//2.当s[i]==')',s[i - 1]==')'时//如果s[i - 1 - dp[i - 1]]=='('//dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]int ans = 0;int n = s.size();vector<int> dp(n, 0);for (int i = 1; i < n; i++) {if (s[i] == ')') {if (s[i - 1] == '(') dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;else if (i - dp[i - 1] > 0 && s[i - 1 - dp[i - 1]]=='(') {dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] >= 2) ? dp[i - 2 - dp[i - 1]] : 0);}}ans = max(ans, dp[i]);}return ans;}
};