先看下题目：
给定一个由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数组成非降子序列，求最长的非降子序列。例如，由12个正整数组成的序列为：48，16，45，47，52，46，36，28，46，69，14，42请在序列中删除若干项，使剩下的项为非降(即后面的项不小于前面的项)序列，剩下的非降序列最多为多少项？
这道题第一次做是会做的，刷了两天动态规划类题目，第二次做的时候，不会了 (￣_,￣ )，难道dp类题目刷的不够多？
我们知道，动态规划类题目通常分为三个步骤求解：
1. 分阶段。
2. 状态迁移方程。
3. 求取最优解。
第一次做思考了一下就想到方案了，第二次做的时候没思考就想着套动态规划的解题过程，结果把自己套没了...... 看来解决问题不能套公式，灵活处理最重要。
对于这套题目，设数组a[n], 假设M[i]表示从i~n的最长非降数列长度，边界情况是m[n] = 1；从后往前遍历，求m[i]，对于任意一个j, i < j < n;
如果a[i] <= a[j]，则m[i] = m[j] + 1; 遍历[i+1, n]，找到最大的m[i]即可。
状态迁移方程得到了，求取最优解序列的时候，遍历m[i]，找到最大值i，顺着i打印即可。保持后续的打印数字m[i]递减。
这道题的c代码：
/** 最长非降子序列* * m[i] = MAX(m[j]) + 1; a[i] > a[j] && j < i;*/#include <stdio.h>#include <time.h>#include <stdlib.h>#define MAX(a, b) ((a) > (b) ? (a) : (b))void main(){int a[30] = {0}, n, i,j,k,max,m[30] = {0}, c[30];printf("input total numbers :"); scanf("%d", &n);if (n > 30){printf("invalid number\n");return;}//随机生成一些数字srand(time(NULL));for (i = 0; i < n; i++)a[i] = rand()%20 + 1;printf("无序数列为：");for (i = 0; i < n; i++)printf("%d ", a[i]);printf("\n");//边界初始化m[n-1] = 1;c[n-1] = n-1;//状态递推for (i = n- 2; i >= 0; i--){m[i] = 1;c[i] = i;for (j = n - 1; j > i; j--){if (a[i] <= a[j]){if (m[i] < m[j] + 1){m[i] = m[j] + 1;c[i] = j;}}}}//打印最优值max = 0;for (i = 0; i < n; i++){//printf("%d ", m[i]);if (m[i] > max){max = m[i];k = i;}}printf("最长非降子数列长度为：%d\n", max);while (c[k] != k){printf("%d ", a[k]);k = c[k];}printf("%d \n",a[k]);return;}
参考资料：
1.数据结构: C语言版/ 严蔚敏，吴伟民编著
=============================================================================================
Linux应用程序、内核、驱动开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。
