解题思路:转化最长上升子序列和最长下降子序列的最大值
注意事项:
参考代码:
#include<iostream> #include<algorithm> #include<cstring> const int N = 1e3 + 10; int a[N],f[N],g[N]; using namespace std; int main() { int t, n ; cin >> t; while(t --){ memset(a, 0, sizeof a); memset(f, 0, sizeof f); memset(g, 0, sizeof g); cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++){ f[i] = 1; g[i] = 1; for(int j = 1; j < i ; j ++){ if(a[i] < a[j]){ f[i] = max(f[i], f[j] + 1); } if(a[i] > a[j]){ g[i] = max(g[i], g[j] + 1); } } } int res = 0; for(int i = 1; i <= n; i ++) { if(res < f[i]) res = f[i]; if(res < g[i]) res = g[i]; } cout << res << endl; } return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题5.7 (C++代码)浏览:855 |
母牛的故事 (C语言代码)浏览:932 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:528 |
【偶数求和】 (C语言代码)浏览:557 |
字符逆序 (C语言代码)浏览:643 |
母牛的故事 (C语言代码)浏览:944 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1420 |
1052题解(链表操作)浏览:674 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:1220 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:467 |