你这个思路是正确的
但是时间复杂度太高了
换个思路
by chenhaotian0219 @ 2023-07-12 14:53:00
@[qz5zxieliyi](/user/1004366)
数组好像不够大
然后每次不满足条件时直接跳转,就省时间
```
#include<iostream>
using namespace std;
int m=0,n,a[1000001];
int main() {
cin>>n;
for(int i=1; i<=n; i++)cin>>a[i];
for(int i=1; i<=n; i++) {
int t=1;
// cout<<i<<endl;
for(int j=i+1; j<=n; j++) {
if(a[j]>a[j-1]) {
t++;
} else {
i=j-1;
break;
}
}
if(t>m) m=t;
}
cout<<m;
return 0;
}
```
by Aakkosetsumussa @ 2023-07-12 14:54:49
@[Aakkosetsumussa](/user/400468)
谢谢大佬 ac了
by qz5zxieliyi @ 2023-07-12 14:57:32
正解是:
从头过一遍 如果不是上升子序列 就新开一个
什么意思呢?
你这个算法长的原因主要是
1 2 3 4 5 3
实际上 很明显2345 345 45 5都没有12345长
但是你都算了一遍
实际只需要判断12345和3谁长
那么我们一个最长上升子序列的开头最好是上一个上升子序列的结尾
因为如果再往后 肯定会变少
但是再往前就往前不了 如果开头可以是上一个上升子序列,那么这两个上升子序列就是一个上升子序列了 矛盾
样例这样算
这题的样例数据 1 2 3 2 4 5 6 8 5 9
当前子序列长度 1 2 3 1 2 3 4 5 1 2
所以一共3个有可能成为最长上升子序列的上升子序列 一个长度3 一个长度5 一个长度2
所以输出5
代码你可以去看题解 我这边不写了 有事
给个关注呗
by chenhaotian0219 @ 2023-07-12 14:59:39
@[qz5zxieliyi](/user/1004366)
by chenhaotian0219 @ 2023-07-12 15:00:04
@[chenhaotian0219](/user/553671)
懂了懂了
谢谢大佬
by qz5zxieliyi @ 2023-07-12 15:10:15