解题思路:转化最长上升子序列和最长下降子序列的最大值
注意事项:
参考代码:
#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语言程序设计教程(第三版)课后习题8.9 (C语言代码) 用函数传参的方法浏览:4091 |
Biggest Number (C++代码)回溯法浏览:1616 |
数组输出 (C语言代码)错误???浏览:570 |
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:1095 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:886 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:561 |
1126题解浏览:599 |
1035 题解浏览:786 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:537 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:559 |