题解 | #牛牛的数列#
牛牛的数列
https://ac.nowcoder.com/acm/problem/13134
定义[start1, end1]为第一个严格递增子序列，[start2, end2]为第二个严格递增子序列，start2 = end1 + 1;
当start1 == end1, start2 == end2时，说明严格递增子序列只有1个数；
两个严格递增子序列可以合并的情况：
1. start1 == end1,第一个严格递增子序列只有一个数，可以变化该数，使得这个数小于第二个严格递增子序列的最小的数，也就是nums[start2];
2. start2 == end2,第二个严格递增子序列只有一个数，可以变化该数，使得这个数大于第一个严格递增子序列的最大的数，也就是nums[end1];
3. 当start1 != end1时，说明第一个严格递增子序列至少有2个数，当start2 != end2时，说明第二个严格递增子序列至少有2个数；
当第二个严格递增子序列的第二个数 > 第一个严格递增子序列最大的数 + 1，即nums[start2 + 1] > nums[end1] + 1,可以把nums[start2]变化，
使得这两个子序列可以合并；
当第一个严格递增子序列的倒数第二个数 < 第二个严格递增子序列最小的数 - 1，即nums[end1 - 1] < nums[start1] - 1,可以把nums[end1]变化，
使得这两个子序列可以合并；
两个严格递增子序列不能合并时：
此时的答案是这两个子序列长度最长的长度 + 1，1是较短的子序列的拿出最大的数或者最小的数拼接到长的序列上。
迭代更新[start1, end1]和[start2, end2]，找到答案最大的值。
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<int> &nums) {
int n = nums.size();
if (n <= 0)
return 0;
int res = 0;
int start1 = 0, end1 = start1;
while (end1 < n - 1 && nums[end1] < nums[end1 + 1])
end1++;
// end1 == n - 1代表整个数组严格递增
if (end1 == n - 1)
return end1 - start1 + 1;
// end1 < n - 1 保证[start2, end2]至少有数字
while (end1 < n - 1) {
int start2 = end1 + 1;
int end2 = start2;
while (end2 < n - 1 && nums[end2] < nums[end2 + 1])
end2++;
if (start1 == end1 || start2 == end2 || nums[start2 + 1] - nums[end1] > 1 || nums[start2] - nums[end1 - 1] > 1)
res = max(res, end2 - start2 + end1 - start1 + 2);
else
res = max(max(end2 - start2, end1 - start1) + 2, res);
start1 = start2;
end1 = end2;
}
return res;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
cout << solution(nums) << endl;
return 0;
}
查看13道真题和解析
