动态规划法


最长单调递增子序列问题的定义:      设计一个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 [crayon-59c3df0230d71881974714/] Output [crayon-59c3df0230d81701537320/] Sample Input [crayon-59c3df0230d87761668964/] Sample Output [crayon-59c3df0230d8c754452084/] C程序: #include <stdio.h> #include <stdlib.h> void findAllMax(int *,int *,int *,int); void trackBack(int *,int *,int *,int); int main(void) { //数组的长度 int len; scanf(“%d”, &len); //存储每个位置的最长子序列 […]

动态规划法 寻找最长单调递增子序列