参考链接：
leetcode——》最长递增子序列
leetcode中文——》最长递增子序列
给你一个整数数组 nums ，找到其中 最长 严格 递增子序列 的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
整数数组 nums ：[3 , 1 , 2 , 6 , 4 , 5]
数组下标 ： 0 1 2 3 4 5
最长递增子序列 ： [1 , 2 , 3 , 5]
长度 ：4
整数数组 nums ：[6 , 3 , 1 , 3 , 4 , 9]
数组下标 ： 0 1 2 3 4 5
最长递增子序列 ： [1 , 3 , 4]
长度 ：3
整数数组 nums ：[3 , 1 , 2 , 6 , 4 , 5]
数组下标 ： 0 1 2 3 4 5
辅助数组dp ：[ 1 , 1 , 2 , 3 , 3 , 4 ]
最长递增子序列 ： [1 , 2 , 4 , 5 ]
长度 ：4
根据整数数组 nums，生成辅助数组 dp dp[0] = 以mus[0]为结尾的最长递增子序列长度 = [3] = 1 dp[1] = 以mus[1]为结尾的最长递增子序列长度 = [1] = 1 dp[2] = 以mus[2]为结尾的最长递增子序列长度 = [1,2] = 2 dp[3] = 以mus[3]为结尾的最长递增子序列长度 = [1,2,6] = 3 dp[4] = 以mus[4]为结尾的最长递增子序列长度 = [1,2,4] = 3 dp[5] = 以mus[5]为结尾的最长递增子序列长度 = [1,2,4,5] = 4解答过程二
整数数组 nums ：[3 , 2 , 1 , 4 , 6 , 5 ]
数组下标 ： 0 1 2 3 4 5
辅助数组dp ：[1 , 1 , 1 , 2 , 3 , 3 ]
辅助数据ends ：[ 1 , 4 , 5]
最长递增子序列 ： [1 , 4 , 5 ]
长度 ：3
根据整数数组 nums，生成辅助数组 ends （只是为了给dp加速，它不是最长递增子序列） ends[i] = 在所有长度为i+1的递增子序列里，最小的结尾 dp[0] = 1 ends[0] = 3 = 在所有长度为1的递增子序列里，最小的结尾是3 dp[1] = 1 ends[0] = 2 = 在所有长度为1的递增子序列里，最小的结尾原来是3，现在变成2 dp[2] = 1 ends[0] = 1 = 在所有长度为1的递增子序列里，最小的结尾原来是2，现在变成1 dp[3] = 2 ends[1] = 4 = 在所有长度为2的递增子序列里，最小的结尾是4 dp[4] = 3 ends[2] = 6 = 在所有长度为3的递增子序列里，最小的结尾是6 dp[5] = 3 ends[2] = 5 = 在所有长度为3的递增子序列里，最小的结尾是原来6，现在变成5
整数数组 nums ：[4 , 1 , 2 , 6 , 4 , 7 , 3 ]
数组下标 ： 0 1 2 3 4 5 6
辅助数组dp ：[1 , 1 , 2 , 3 , 3 , 4 , 3 ]
辅助数据ends ：[ 1 , 2 , 3 , 7]
最长递增子序列 ：[ 1 , 2 , 4 , 7]
长度 ：4
根据整数数组 nums，生成辅助数组 ends （只是为了给dp加速，它不是最长递增子序列）
ends[i] = 在所有长度为i+1的递增子序列里，最小的结尾
dp[0] = 1
ends[0] = 4 = 在所有长度为1的递增子序列里，最小的结尾是4
dp[1] = 1
ends[0] = 1 = 在所有长度为1的递增子序列里，最小的结尾原来是4，现在变成1
dp[2] = 3
ends[1] = 2 = 在所有长度为2的递增子序列里，最小的结尾是2
dp[3] = 3
ends[2] = 6 = 在所有长度为3的递增子序列里，最小的结尾是6
dp[4] = 3
ends[2] = 4 = 在所有长度为3的递增子序列里，最小的结尾原来是6，现在变成4
dp[5] = 4
ends[3] = 5 = 在所有长度为4的递增子序列里，最小的结尾是7
dp[6] = 3
ends[2] = 3 = 在所有长度为3的递增子序列里，最小的结尾原来是4，现在变成3
整数数组 nums ：[5 , 6 , 7 , 1 , 2 , 3 , 4 ]
数组下标 ： 0 1 2 3 4 5 6
辅助数组dp ：[1 , 2 , 3 , 1 , 2 , 3 , 4 ]
辅助数据ends ：[ 1 , 2 , 3 , 4]
最长递增子序列 ：[ 1 , 2 , 3 , 4]
长度 ：4
根据整数数组 nums，生成辅助数组 ends （只是为了给dp加速，它不是最长递增子序列）
ends[i] = 在所有长度为i+1的递增子序列里，最小的结尾
dp[0] = 1
ends[0] = 5 = 在所有长度为1的递增子序列里，最小的结尾是5
dp[1] = 2
ends[0] = 1 = 在所有长度为2的递增子序列里，最小的结尾是6
dp[2] = 3
ends[1] = 7 = 在所有长度为3的递增子序列里，最小的结尾是7
dp[3] = 1
ends[2] = 1 = 在所有长度为1的递增子序列里，最小的结尾原来是5，现在变成1
dp[4] = 2
ends[2] = 2 = 在所有长度为2的递增子序列里，最小的结尾原来是6，现在变成2
dp[5] = 3
ends[3] = 3 = 在所有长度为3的递增子序列里，最小的结尾原来是7，现在变成3
dp[6] = 4
ends[2] = 4 = 在所有长度为4的递增子序列里，最小的结尾是4
代码示例
public class Code03_LIS {
public static int lengthOfLIS(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int[] ends = new int[arr.length];
ends[0] = arr[0];
int right = 0;
int l = 0;
int r = 0;
int m = 0;
int max = 1;
for (int i = 1; i < arr.length; i++) {
l = 0;
r = right;
while (l <= r) {
m = (l + r) / 2;
if (arr[i] > ends[m]) {
l = m + 1;
} else {
r = m - 1;
}
}
right = Math.max(right, l);
ends[l] = arr[i];
max = Math.max(max, l + 1);
}
return max;
}
}
