题解分享
题解分享简介
最长不下降子序列 - 题解
```
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1100;
int dp[N]; //dp[i]表示一第i个数为结尾的最长序列长度
int a[N]; //用来存储数组
signed main(){
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++){
cin >> a[i];
dp[i] = 1; //因为每一个数都可以单独作为一个不下降序列，长度即为1
}
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j < i ; j ++)
if(a[j] < a[i])
dp[i] = max(dp[i] , dp[j] + 1);
int ans = 0;
for(int i = 1 ; i <= n ; i ++)
ans = max(ans , dp[i]);
cout << ans << '\n';
return 0;
}
```
查看全文
0
0
0
4
最长不下降子序列 - 题解
```python
input = open(0).readline
n = int(input())
a = list(map(int,input().split()))
dp = [0]*n + [0]
for i in range(n):
# 找比a[i]小的中dp最大的
b = max(list(filter(lambda x:a[x] <= a[i], range(i))) or [-1],key=lambda a:dp[a])
dp[i] = dp[b] + 1
print(max(dp))
```
查看全文
0
0
0
3
