最长上升子序列

题目描述：
给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例：
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

第 1 步：定义状态
由于一个子序列一定会以一个数结尾，于是将状态定义成：dp[i] 表示以 nums[i] 结尾的「上升子序列」的长度。注意：这个定义中 nums[i] 必须被选取，且必须是这个子序列的最后一个元素。

第 2 步：考虑状态转移方程
遍历到 nums[i] 时，需要把下标 i 之前的所有的数都看一遍；
只要 nums[i] 严格大于在它位置之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列；
因此，dp[i] 就等于下标 i 之前严格小于 nums[i] 的状态值的最大者+1。
语言描述：在下标 i 之前严格小于 nums[i] 的所有状态值中的最大者+1。

符号描述：

image.png

第 3 步：考虑初始化
dp[i] = 1，11 个字符显然是长度为 11 的上升子序列。

第 4 步：考虑输出
这里要注意，不能返回最后一个状态值；
还是根据定义，最后一个状态值只是以 nums[len - 1] 结尾的「上升子序列」的长度；
状态数组 dp 的最大值才是最后要输出的值。

image.png

第 5 步：考虑状态压缩。
遍历到一个新数的时候，之前所有的状态值都得保留，因此无法压缩。

改进算法:
第 1 步：定义新状态（特别重要）
tail[i] 表示长度为 i + 1 的所有上升子序列的结尾的最小值。

说明：

tail[0] 表示长度为 11 的所有上升子序列中，结尾最小的那个元素的数值，以题目中的示例为例 [10, 9, 2, 5, 3, 7, 101, 18] 中，容易发现长度为 2 的所有上升子序列中，结尾最小的是子序列 [2, 3] ，因此 tail[1] = 3
下标和长度有一个 1 的偏差；

第2步：思考状态转移方程
从直觉上看，tail也是一个严格上升的数组，证明如下：
假设对于任意的下标i < j，存在某个tail[i] >= tail[j]。
对于此处的tail[i]而言，对应一个上升子序列[a0,a1,...,ai],依据定义tail[i] = ai;
对于此处的tail[j]而言，对应一个上升子序列[b0,b1,...,bi,...,bj],依据定义tail[j] = bj;
由于tail[i] >= tail[j],等价于ai >= bj，但是bi严格小于bj，因此ai >= bj > bi;
然而上升子序列[b0,b1,...bi]是一个长度为i + 1但结尾更小的数组，这与ai的最小性相矛盾，证毕。

算法的执行流程
1、设置一个数组 tail，初始时为空；

注意：数组 tail 虽然是有序数组，但它不是问题中的「最长上升子序列」（下文还会强调），不能命名为 LIS。有序数组 tail 只是用于求解 LIS 问题的辅助数组。

2、在遍历数组 nums 的过程中，每来一个新数 num，如果这个数严格大于有序数组 tail 的最后一个元素，就把 num 放在有序数组 tail 的后面，否则进入第 3 点；

注意：这里的大于是「严格大于」，不包括等于的情况。

3、在有序数组 tail 中查找第 1 个等于大于 num 的那个数，试图让它变小；

如果有序数组 tail 中存在等于 num 的元素，什么都不做，因为以 num 结尾的最短的「上升子序列」已经存在；
如果有序数组 tail 中存在大于 num 的元素，找到第 1 个，让它变小，这样我们就找到了一个结尾更小的相同长度的上升子序列。
说明：我们再看一下数组 tail[i] 的定义：长度为 i + 1 的所有最长上升子序列的结尾的最小值。因此，在遍历的过程中，我们试图让一个大的值变小是合理的。

这一步可以认为是「贪心算法」，总是做出在当前看来最好的选择，当前「最好的选择」是：当前只让让第 1 个严格大于 nums[i] 的数变小，变成 nums[i]，这一步操作是“无后效性”的。

由于是在有序数组中的操作，因此可以使用「二分查找算法」。

4、遍历新的数 num ，先尝试上述第 2 点，第 2 点行不通则执行第 3 点，直到遍历完整个数组 nums，最终有序数组 tail 的长度，就是所求的“最长上升子序列”的长度。

第 3 步：思考初始化
dp[0] = nums[0]，在只有 1 个元素的情况下，它当然是长度为 1 并且结尾最小的元素。

第 4 步：思考输出
数组 tail 的长度，上文其实也已经说了，还是依据定义，tail[i] 表示长度固定为 i + 1 的所有「上升子序列」的结尾元素中最小的那个，长度最多就是数组 tail 的长度。

第 5 步：思考状态压缩
无法压缩。

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Java代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if(len <= 1) return len;

        int[] dp = new int[len];
        Arrays.fill(dp ,1);
        for(int i = 1;i < len;i++) {
            for(int j = 0;j < i;j++) {
                if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        int res = 1;
        for(int i = 0;i < len;i++) res = Math.max(res, dp[i]);
        return res;
    }

    public int lengthOfLISAdvanced(int[] nums) {
        int len = nums.length;
        if(len < 2) return len;

        //tail数组的定义：长度为i + 1的上升子序列的末尾最小是几
        int[] tail = new int[len];
        //遍历第一个数直接放到tail的开头
        tail[0] = nums[0];
        //end表示tail的最后一个已经被赋值的元素的索引
        int end = 0;

        for(int i = 1;i < len;i++) {
            //case 1:比tail实际有效的末尾还大
            if(nums[i] > tail[end]) {
                //直接添加在那个元素后面，end先加1
                end++;
                tail[end] = nums[i];
            } else {
                //找到第一个大于等于nums[i]的元素，尝试让该元素更小
                int left = 0;
                int right = end;
                while(left < right) {
                    int mid = left + ((right - left) >>> 1);
                    if(tail[mid] < nums[i]) left = mid + 1;
                    else right = mid;
                }

                //走到这里是因为case1的反面，因此一定能找到一个大于等于nums[i]的元素
                tail[left] = nums[i];
            }


        }
        end++;
        return end;
    }
}