最长单调递增子序列问题的定义： 设计一个O(n2)时间的算法，找出由n个数组组成的序列的最长单调递增子序列。 子问题的定义： 对于求解N规模的数组，n-1,n-2,…,1 长度的数组构成了问题的子问题，子问题的详细定义是：求解以第n-1,n-2,…,1 个元素为最大值的最长子序列。 最优子结构： 第n个元素的最长子序列的长度是基于前n-1个元素最长子序列的基础之上，也就是第n个元素的最长子序列长度，是前n个元素的中最长的子序列长度+1。 解决的办法： 从第1个元素开始进行循环，不断地求出1,2,3,..,n元素为最大值的最长子序列长度，然后通过回溯查找最长子序列。 具体算法： Input 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开 Output 最长单调递增子序列，数字之间用空格格开 Sample Input 5 1 3 5 2 9 Sample Output 1 3 5 9 C程序： #include <stdio.h> #include <stdlib.h> void findAllMax(int *,int *,int *,int); void trackBack(int *,int *,int *,int); […]