求序列中最长递增子序列的长度

#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] = 1
a[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;
}