第1题 最长上升序列II
有N个数放在一个圆周上,可以从任意一个位置开始按照顺时针方向访问数据一圈,沿途可以挑选一些数,要求这些数是上升的(一个比一个大)。问最多能选多少个数?
输入格式
第一行:1个整数N,范围在1到100
第二行有N个整数,每个数范围在1到1000000
输出格式
最多挑选的个数。
输入/输出例子1
输入:
8
2 9 3 5 6 7 1 5
输出:
6
用c++98咋写??
第1题 最长上升序列II
有N个数放在一个圆周上,可以从任意一个位置开始按照顺时针方向访问数据一圈,沿途可以挑选一些数,要求这些数是上升的(一个比一个大)。问最多能选多少个数?
输入格式
第一行:1个整数N,范围在1到100
第二行有N个整数,每个数范围在1到1000000
输出格式
最多挑选的个数。
输入/输出例子1
输入:
8
2 9 3 5 6 7 1 5
输出:
6
用c++98咋写??
思路,将这个数组复制一份,首尾相接
然后依次判断是否是上升序列
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int arr[n * 2];
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
arr[i] = arr[i + n] = x;
}
int ma = 0;
int curr = 1;
for (int i = 1; i < n * 2; i++)
{
if (arr[i] > arr[i - 1])
curr += 1;
else
curr = 1;
if (curr > ma) ma = curr;
}
cout << (ma > n ? n : ma);
return 0;
}