动态规划（二）——最长递增子序列（LIS）

---

前言

在遥远的上一篇，我们介绍了动态规划的第一个问题——背包问题。这篇，我们接着介绍另一个初级问题——最长递增子序列(LIS)。

问题简述

给定一个数字序列 $a_1, a_2, \ldots, a_n$ ，求其中最长的递增子序列长度。举个栗子，现在有序列 $2, 3, 5, 4, 1, 6$ ，那么最长递增子序列就是 $2, 3, 5, 6$ 和 $2, 3, 4, 6$ ，长度为4，我们不关注子序列的元素在原序列中是否相邻。

问题分析

根据上一篇的经验，要解决动态规划问题，关键是找出状态及状态转移方程。现在，我们循着这个思路，尝试解决。
首先是状态，我们可以怎样定义状态呢？首先想到的，是把前i个数字序列的LIS长度d[i]作为状态。找到状态，接着找状态转移方程。假设我们已经找到了d[1]，d[2]，…，d[i]，如何找出d[i+1]呢？我们发现，要确定d[i+1]，需要知道$ a_{i+1} $与前面数字的大小。这就带来一个问题——我们在记录d[i]时，并没有记录d[i]对应的末尾数字，这让我们陷入困境。
我们需要更新状态的定义。
根据上面的分析，我们把状态d[i]定义为：前i个数字序列，且以$ a_i $作为结尾的LIS长度。那么，d[i+1]就是d[1]，d[2]，…，d[i]中末尾数字小于$ a_{i+1} $的最大值，即$ d[i+1]=max \lbrace d[k] | a_k<a_{i+1}, k \in (1, i) \rbrace $。
在给出代码之前，先插播一下我关于使用循环还是递归的一些看法。在上一篇中，我们给出了递归与循环两种方式的实现，但是个人感觉递归更加容易理解一点，因为那里有硬性约束——背包容量，适合用递归自顶向下考虑；而这里，我们没有什么硬性约束，且为了得到一个状态，需要预先知道前面所有的状态值，所以，适合用循环自底向上考虑。
下面我们给出代码。

问题解决

public static int LIS(int[] nums, int index) {
	int[] d = new int[nums.length+1];
	for (int i = 1; i <= nums.length; i++) {
    	// d[i]表示以第i个数字结尾的最长递增子序列长度
    	if (i == 1) d[i] = 1;
    	// 遍历d[j]，找出最大的d[j]，且满足第j个数字小于第i个数字
    	// 这样，d[i]=d[j]+1，否则d[i]=1
    	for (int j = 1; j < i; j++) {
    		if (nums[j-1] < nums[i-1] && d[j]+1 > d[i]) d[i] = d[j]+1;
    	}
    	d[i] = d[i] > 1 ? d[i] : 1;
	}
	// 遍历各个最长递增子序列长度值，返回前index个数字中最长的递增子序列长度
	int max = 0;
	for (int i = 1; i <= index; i++) {
		if (max < d[i]) max = d[i];
	}
	return max;
}

---