题目大意：最大上升子列

LIS最大上升子列
朴素算法：O(n*n)
子问题：每次找到一个从前面到以i位置为结束的上升子列,而i位置要往前面找一个最大的上升子列dp[j],进而把问题规模缩小到j
状态：dp[i]->以i位置元素为结束的上升子列的长度
转移方程：dp[i]=max(dp[i],dp[j]+1)    dp[j]->表示在j段中以j为结束的上升子列   （i>j,data[i]>data[j]）
dp[]要初始化到1，因为因为每个位置最小上升子列都是1即它本身

#include<stdio.h>
#define MAX 100010
int data[MAX],dp[MAX];

int main()
{
	int i,j,n,m=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&data[i]);
		dp[i]=1;
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<i;j++)        //这里注意要到i-1位置，因为如果遍历到i相当于子列尾部有两个data[i]错误，从结果上看到j==i一定有dp[i]<dp[j]+1
		{
			if(data[i]>data[j] && dp[i]<dp[j]+1)
				dp[i]=dp[j]+1;
		}
		if(m<dp[i])
			m=dp[i];
	}
	printf("%d\n",m);
}
/*
LIS最长上升子列
二分算法:O(n*logn)
*/
int find(int num,int left,int right)   //通过二分法找到一个刚好比num大的数
{
	int mid;
	while(left<=right)
	{
		mid=(left+right)/2;
		if(dp[mid]<=num) left=mid+1;
		else right=mid-1;
	}
	return left;
}
int DP(int n)
{
	int i,len,s;
	dp[1]=data[1];
	len=1;
	for(i=2;i<=n;i++)
	{
		if(data[i]>dp[len])
		{
			len++;
			dp[len]=data[i];
		}
		else//通过二分查找一个刚好比data[i]大的数，然后替换它，动态地使整个子列挨得更紧
		{
			s=find(data[i],1,len);
			dp[s]=data[i];
		}
	}
	return len;
}
int main()
{
	int i,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&data[i]);
	printf("%d\n",DP(n));
	return 0;
}
7
1 7 3 5 9 4 8
添加长度后：1 7
##更替前：1 7
##更替后：1 3
添加长度后：1 3 5
添加长度后：1 3 5 9
##更替前：1 3 5 9
##更替后：1 3 4 9
##更替前：1 3 4 9
##更替后：1 3 4 8
4

第二种算法可以总结成一个模板，我觉得这种思想是贪心思想，每次都使整个子列更紧密，为什么要这样做呢？因为前面挨得越紧就相当于前面的最大一个数可能越小，导致整个数列能够把最大值往下降，子列就更有变长的希望。