求序列中最长递增子序列的长度
#include <stdio.h>#define MAXNUM 100/*函数功能:求解序列中的最大递增子序列的中包含的元素个数算法说明:用到了动态规划问题,分解子问题b数组是用来存储每一个子序列中的最大递增子序列求具有n个元素的序列中的最大递增自序列问题分解为a[0], a[0] a[1], a[0] a[1] a[2], a[0] a[1] a[2]...a[m] m< n个子序列求其中的最大递增子序列a[0]显然是递增的 所以b[0] = 1a[0] a[1]求其中的最大递增自序列要依靠 a[0]如果 b[0] + 1 > max则让max = b[0]动态规划使用条件:1. a[0]是递增的 最大递增自序列元素个数为1 是确定的 最优的2. a[0]....a[j] (j < n) 最大递增子序列的元素个数依赖于 a[0]...a[j - 1]的最大子序列 只对当前状态保持最优依次递推下去 a[0]....a[j]也是最优的*/int main(){int a[MAXNUM], b[MAXNUM];int n, i, j, max;scanf("%d", &n);for(i = 0; i < n; i++){scanf("%d", &a[i]);}b[0] = 1;for(i = 1; i < n; i++){max = 0; //代表此次最大的升序列for(j = i - 1; j >= 0; j--){if(a[j] < a[i] && max < b[j] + 1){max = b[j];}}b[i] = max + 1;}max = b[0];for(i = 1; i < n; i++){if(b[i] > max)max = b[i];}printf("最大子序列个数为:%d\n", max);return 0;}