最长上升子序列

视频讲解：最长上升子序列_哔哩哔哩_bilibili 

---

解题思路：

1.最长上升子序列的含义是从给定的数中选取尽量多的数字形成单调递增的序列

2.可以把以每一个数字形成单调结尾的方案数看待成一个子问题，然后对后面的子问题提供最优解

3.设定状态，dp【x】为以第x个位置上的数字结尾的序列长度

4.状态转移，如果以第x个位置上的数字结尾，前面a[j]

5.初始化dp数组为1，因为本身就是一个单调递增的序列

---

#include
using namespace std;
int a[10010],dp[10010];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)//输入元素到数组中 
	cin>>a[i];
	
	for(int i=1;i<=n;i++)//初始化dp数组，最小值都为1 
	dp[i]=1;
	
	for(int i=2;i<=n;i++)//从第二项开始转移 
	{
		for(int j=1;j<=i;j++)//从他前面开始找 
		{
			if(a[i]>a[j])//如果可以a[i]结尾 
			{
				dp[i]=max(dp[j]+1,dp[i]);//状态转移方程 
			}
		}
	}
	
	for(int i=1;i<=n;i++)//输出方案数 
	cout<" ";
	
	return 0;
}

---

算法优化：

1.上面的思路本质上是在暴力枚举，把每个状态都比较一次，所以时间复杂度是O（n*n），在其中，有很多是没有必要去枚举的，导致浪费了更多的时间，当数据量较大的时候便超时

2.可以利用贪心的思想，如果设置f【i】为此时子序列长度为i的时候末尾的元素值，那么这个元素值较小的时候，才能为后面空出更多的空间

3.设置初始状态f【1】=a【1】，即第一个元素本身就是一个数位，从第二项开始，判断如果a[i]>f【len】的，说明子序列的长度又可以加1，先把a【i】放在新序列的末尾，长度len++,

 即f【++len】=a【i】；

4.当a【i】是小于f【len】的时候，说明他其实可以作为前面子序列中的末尾值，举个例子：

       原序列为：1 3 2 4 5，1作为上升子序列的第1项即f【1】=1;

                         3作为上升子序列的第二项f【2】=3

                         当到达2的时候，发现2比3小，那么此时的2完全可以取代3，因为2可以为后面腾                             出更多的空 间，所以f【2】=2

                        （因为这里只要求我们输出最长上升子序列的长度，所以不必考虑第二个位                                      置 到底是谁，只要确定目前有2个上升的序列长度即可！）

5.那么如何去查找呢？将此时更小的a【i】放到最合适的位置上，这里采用二分查找的方法（也就是真正降低时间复杂度的关键O（nlogn）），因为形成的f【len】已经值单调递增的序列，所以可以利用在排好序的序列中，将a【i】一直往前找，

举个例子：此时1,4,5已经是排好序的子序列，当前最长上升长度为3，也就是5的下标，遍历2的时候，发现比前面的值小，贪心思想来说，2更应该作为末尾值，所以往前找，直到找到比它刚刚小的值，然后放入到该位置后面即可

6.最后输出f数组的长度即为最长上升子序列的长度

#include
using namespace std;
const int MAXN=99999999;
int a[100010],f[100010];
 
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=MAXN; //设置最大值，方便后续替换 
	}
	
	f[1]=a[1];//以第一个元素作为子序列的第一个值 
	int len=1;//记录当前上升子序列的长度 
	
	for(int i=2;i<=n;i++)
	{
		int low=0,high=len,mid;//设置二分查找的区间 
		
		if(a[i]>f[len])//如果当前值是大于排好序的末尾元素值的 
		f[++len]=a[i];//加长子序列的长度，将该值作为该位置的末尾元素值
		else
		{
			
			while(low//二分查找 当low>=high停止循环 
			{
				mid=(high+low)/2;
				
				if(f[mid]>a[i])//如果中间值大于a[i]，继续往前找 
				high=mid;//上限更新 
				else//否则的话 
				low=mid+1;//下限更新 
			}
			f[low]=min(f[low],a[i]);//更新末尾数字 
		} 
	}
	cout<
	return 0;
}