本文共 1604 字，大约阅读时间需要 5 分钟。

最长递增子序列（Longest increasing subsequences）

问题描述：

       the input is a sequence of numbers a1, a2, ……, an. A subsequence is any subset of these numbers taken in order, of the form ai1, ai2, ……, aik where 1 <= i1 <= i2 <= … ik <= n, and an increasing subsequence is one in which the numbers are getting strictly larger.（标蓝的数字均为下标）

The task is to find the increasing subsequence of greatest length. For instance, the longest increasing subsequence of 5, 2, 8, 6, 3, 6, 9, 7 is 2, 3, 6, 9.

❗算法思想❗：

       定义 lis[i] 为截至到第 i 个数字为止，最长递增子序列的长度，path[i] 为截至到第 i 个数字为止，最长递增子序列中 i 的前一个元素。

       初始状态：lis[0] = 1；

       决策方程： lis[i] = max( if (lis[i] > lis[j]), lis[i] = lis[j] + 1; else, lis[i] = lis[j+1])；

       问题解：lis[k], k = lenght - 1。

代码✍：

#include 
   
    #include 
    
     using namespace std;int main(){	vector
     
       seq;	//输入序列	while (1)	{		int temp;		cin >> temp;		seq.push_back(temp);		char tmp = getchar();		if (tmp == '\n')		{			break;		}	}	int length = int(seq.size());	vector
      
        lis(length);				//lis[i]存储以seq[i]为终点时最长递增子序列的大小	vector
       
         path(length);				//path[i]存储以seq[i]为终点时最长递增子序列的上一个数字	int Lis[2] = {1, 0};					//Lis[0]存储最长递增子序列的长度，Lis[1]存储最长递增子序列终点数的下标	for (int i = 0; i < length; ++i)	{		//将lis数组初始化为1		lis[i] = 1;		//将path数组初始化为下标值		path[i] = i;				for (int j = 0; j < i; ++j)		{			if (seq[i] > seq[j])			{				if (lis[j] + 1 > lis[i])				{					lis[i] = lis[j] + 1;					path[i] = j;				}			}		}		if (lis[i] > Lis[0])		{			Lis[0] = lis[i];			Lis[1] = i;		}	}	//输出最长递增子序列(这是倒序输出的！)	int i = Lis[1];	cout << seq[i] << ' ';	while (path[i] != i)	{		cout << seq[path[i]] << ' ';		i = path[i];	}	return 0;}
       
      
     
    
   

转载地址：http://lttai.baihongyu.com/