题目
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Follow up:
Could you improve it to O(n log n) time complexity?
解法思路（一）
什么是子序列？
- 从一个序列中，选几个数字“落下来”，选中的几个数字的相对位置不变；
什么是上升？
- 广义的说，后一个数比前一个数大，就是上升；
- 有些时候，后一个数和前一个数相等，也是上升，这道题中不把相等的情况定义成上升；
一共有多少子序列？
- 如果序列的长度是 1，那么其子序列的个数是 21；
- 如果序列的长度是 2，那么其子序列的个数是 22；
- 如果序列的长度是 3，那么其子序列的个数是 23；
- ...
- 如果序列的长度是 n，那么其子序列的个数是 2n；
暴力解法的时间复杂度
- 长度是 n 的序列的子序列的个数是 2n；
- 对于每个序列，都要遍历一遍，判断其是否是上升的；
- 这样的时间复杂度是 O(2n * n)；
求解空间的本质
- 实际上是给定序列中所有数字的组合；
- 组合的形成过程是这样的：当把一个数字 x 选进组合，下一个要选进组合的数字只能从 x 之后的数字中寻找；
- 组合的背后有一颗组合树，在写递归相关的算法时，需要参照这棵树；
- 关于组合的问题都是可以用递归的方式实现的，通常也都可以用动态规划的方式实现；
动态规划的设计
- 动态规划问题的规模是从小到大的，从最小规模的问题开始求解，并在此基础上，解决更大规模的问题，直到规模达到问题原本的规模；
- LIS(i) 表示 [0...i] 的范围内，选择数字 nums[i] 可以获得的最长上升子序列的长度；
状态转移方程
-
LIS(i) = max(1 + LIS(j) if nums[i] > nums[j]), j < i；
解法实现（一）
动态规划运行的过程用什么记录？
- 用一个数组
int memo[]记录； -
memo[i]表示以nums[i]为结尾的最长上升子序列的长度；
具体是怎么实现动态规划的？
- 随着动态规划过程的进行，用于记录动态规划进度的数组
memo也在“成长”； - 外层循环用以确定每次问题的规模，内层循环是在之前已经求解的范围中，为当前待求的问题提供支撑；
代码实现
package leetcode._300;
import java.util.Arrays;
public class Solution300_2 {
public int lengthOfLIS(int[] nums) {
if(nums.length == 0)
return 0;
// memo[i] 表示以 nums[i] 为结尾的最长上升子序列的长度
int memo[] = new int[nums.length];
Arrays.fill(memo, 1);
for(int i = 1 ; i < nums.length ; i ++)
for(int j = 0 ; j < i ; j ++)
if(nums[i] > nums[j])
memo[i] = Math.max(memo[i], 1 + memo[j]);
int res = memo[0];
for(int i = 1 ; i < nums.length ; i ++)
res = Math.max(res, memo[i]);
return res;
}
}
