*************
C++
TOPIC:673. 最长递增子序列的个数 - 力扣(LeetCode)
*************
先看题目:
中等困难,之前做的是最长递增子序列,跟这个很像,先来复习一下找一下思路:
// 这个逻辑比较的简单
//就是说我直接定义dp数组,代表第i位最长递增数列的个数
//遍历每一个元素
//找到最大值
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size(); // as before
vector<int> dp(n, 1); // initialise the dp
if (n == 0) return 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < i; j++){
if (nums[i] > nums[j]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int max_len = *max_element(dp.begin(), dp.end());
return max_len;
}
};
但是,这个题目是个数,复习的题目是长度。
我有一个天才的想法:
最长长度假设输出的 dp = [ 1, 2, 5, 5, 6, 3]
那我直接在dp里寻找最大元素的个数不就好了嘛。
那么问题就转移到如何在数组里面找到最大元素的个数了。
这个跟之前的某道题有点像,我想不起来了,但是方法我记得:
开始时,max设为数组的第一个元素,count设为1。然后从第二个元素开始遍历:
- 如果当前元素大于max,就更新max为当前元素,并重置count为1。
- 如果当前元素等于max,就count加1。
- 如果当前元素小于max,就跳过。
这部分的代码是:
int n = sizeofdp();
int max = dp[0];
int count = 0;
for (int i = 0; i < n; i++){
if(dp[i] > max){
max = dp[i];
count = 1;
} else if (dp[i] == max){
count++;
}
return count;
然后把这段代码加到上面去。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size(); // as before
vector<int> dp(n, 1); // initialise the dp
if (n == 0) return 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < i; j++){
if (nums[i] > nums[j]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int n = sizeofdp();
int max = dp[0];
int count = 0;
for (int i = 0; i < n; i++){
if(dp[i] > max){
max = dp[i];
count = 1;
} else if (dp[i] == max){
count++;
}
return count;
}
};
这个代码是报错的,直觉上就是不能简单的粘贴复制,因为运算逻辑是从上到下,如果有循环就直接循环,直至跳出循环再往下一行一行的运行,所以初始化以及对一些变量的命名时需要放在最开始,接下来第二个工作就是优化这个代码。
想一下,最开始就要对dp的长度和个数进行初始赋值,这两个都是我要知道的,要让他进行迭代。
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> lengths(n, 1); // 记录以 nums[i] 结尾的最长递增子序列的长度
vector<int> counts(n, 1); // 记录以 nums[i] 结尾的最长递增子序列的个数
};
最主要的记录最长严格递增子串的长度的方法是不变的,对于每一个i,检查从 0 ~ i 位的大小。还有一个冷知识,在同一段代码中,自定义的 i 应该是一致的。
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
vector<int> count(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) { // to order the numbers
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1; // to define the size of the son-string
count[i] = count[j]; //to told the nubmbers
} else if (dp[j] + 1 == dp[i]) {
count[i] += count[j];
}
}
}
}
}
};
到这一步,保证在检查每一个i对应的dp[i]出现的次数,是同一个 i。
接下来就是找到 dp.start() dp.end()的最大值了。
最大值的方法也很简单,
初始化 max 为 dp[0]
遍历每一个 dp[i]
如果 dp[i] > max,
max = dp[i]
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
vector<int> count(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) { // to order the numbers
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1; // to define the size of the son-string
count[i] = count[j]; //to told the nubmbers
} else if (dp[j] + 1 == dp[i]) {
count[i] += count[j];
}
}
}
}
// Find the maximum length in dp
int max_len = dp[0];
for (int i = 1; i < n; i++) {
if (dp[i] > max_len) {
max_len = dp[i];
}
}
}
};
然后就是统计最大值出现的次数:
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
vector<int> count(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) { // to order the numbers
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1; // to define the size of the son-string
count[i] = count[j]; //to told the nubmbers
} else if (dp[j] + 1 == dp[i]) {
count[i] += count[j];
}
}
}
}
// Find the maximum length in dp
int max_len = dp[0];
for (int i = 1; i < n; i++) {
if (dp[i] > max_len) {
max_len = dp[i];
}
}
// Sum the counts where dp[i] == max_len
int result = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == max_len) {
result += count[i];
}
}
return result;
}
};
OK,完成。
标签:count,nums,int,max,递增,个数,++,序列,dp From: https://blog.csdn.net/ElseWhereR/article/details/144131016