C++语言编程 单调递增最长子序列

Question

7-1 单调递增最长子序列
设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
输入格式:

输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开
输出格式:

最长单调递增子序列的长度
输入样例:

在这里给出一组输入。例如：
5
1 3 5 2 9
输出样例:

在这里给出相应的输出。例如：
4

Answer 1

&nbsp;#include&nbsp;<stdio.h> #define&nbsp;MAX_N&nbsp;1000 int&nbsp;dp[MAX_N],&nbsp;a[MAX_N]; int&nbsp;n; void&nbsp;input() { &nbsp;&nbsp;&nbsp;&nbsp;scanf("%d",&nbsp;&n); &nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;n;&nbsp;++i) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf("%d",&nbsp;&a[i]); } int&nbsp;max_(int&nbsp;a,&nbsp;int&nbsp;b) { &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;a&nbsp;>&nbsp;b&nbsp;?&nbsp;a&nbsp;:&nbsp;b; } void&nbsp;slove() { &nbsp;&nbsp;&nbsp;&nbsp;//注意要res保存结果 &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;res&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;n;&nbsp;++i) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;j&nbsp;=&nbsp;0;&nbsp;j&nbsp;<&nbsp;i;&nbsp;++j) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(a[j]&nbsp;<&nbsp;a[i]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[i]&nbsp;=&nbsp;max_(dp[i],&nbsp;dp[j]&nbsp;+&nbsp;1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res&nbsp;=&nbsp;max_(dp[i],&nbsp;res); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;printf("%d\n",&nbsp;res&nbsp;+&nbsp;1); } int&nbsp;main() { &nbsp;&nbsp;&nbsp;&nbsp;input(); &nbsp;&nbsp;&nbsp;&nbsp;slove(); &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; }