怎么解决“规定一个由 n 个正整数组成的序列,如果序列中连续的几个正整数满足 ai+1>ai(后一项大于前一项) ,则称这连续的几个正整数构成的子串为 “起飞串”。蒟蒻很擅长找到数字序列的最长 “起飞串”。但是现在有神秘力量出现,要求必须从数字序列中删除一个数字。我想要知道哪种删除方式能使得剩下的数字保留最长的 “起飞串”。你需要找到所有删除方案下,能保留的最长的 “起飞串” 的长度。输入格式: 总共两行。 第一行包含一个正整数 n,代表数字序列的长度。 第二行为 n 个正整数,输入时中间用空格隔开。 输出格式 仅为一个整数,代表删除一个数字后最长的 “起飞串” 长度。”这个问题 要求内存限制为128MB时间限制为1s 用C++代码实现
时间: 2024-02-28 17:56:55 浏览: 22
这是一个比较典型的动态规划问题。我们可以先正向遍历一遍序列,记录以每一个位置为结尾的最长“起飞串”的长度,记为dp[i]。然后再反向遍历一遍序列,记录以每一个位置为开头的最长“起飞串”的长度,记为dp2[i]。最后,对于每一个位置i,我们可以计算出删除该位置上的数字后,所能得到的最长“起飞串”的长度,记为ans[i],具体方法为:ans[i] = max(dp[i-1], dp2[i+1])。最终答案即为所有ans[i]中的最大值。
时间复杂度为O(n),符合题目要求。
下面是C++代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++)
cin >> nums[i];
vector<int> dp(n, 1); // 记录以每个位置为结尾的最长“起飞串”长度
for (int i = 1; i < n; i++)
{
if (nums[i] > nums[i - 1])
dp[i] = dp[i - 1] + 1;
}
vector<int> dp2(n, 1); // 记录以每个位置为开头的最长“起飞串”长度
for (int i = n - 2; i >= 0; i--)
{
if (nums[i] < nums[i + 1])
dp2[i] = dp2[i + 1] + 1;
}
int res = 0;
for (int i = 0; i < n; i++)
{
int len;
if (i == 0)
len = dp2[i + 1];
else if (i == n - 1)
len = dp[i - 1];
else
len = max(dp[i - 1], dp2[i + 1]);
res = max(res, len);
}
cout << res << endl;
return 0;
}
```