前言

问题：300. 最长递增子序列

本篇文章用于记录对LIS问题的求解思路总结，用到的方法如下：

1. DP：时间复杂度：O(n^2)        2.二分+贪心：O(nlogn)       

3.dfs+回溯：O（2^n）                 4.树状数组优化DP：O(nlogn)    

在明白LIS问题，我们需要懂得一个概念，那就是何为子串，何为子序列的问题。

简单来说，假设你拥有一数字序列，我从其中抽出数字，若你属于连续抽取，取出的数都是相邻的，则为子串，若非连续，则为子序列。

---

LIS的定义

最长上升子序列（简称LIS），也有些时候，求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。

那什么是LIS问题呢，简单来说，假设我给你一个数字序列，如果这个序列中，存在这样一个子序列，该子序列中的数成递增现象，则为上升子序列，而LIS则是求其中最长的子序列，例子如下：

比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)

---

方法一：DP

我们都知道，动态规划的一个特点就是当前解可以由上一个阶段的解推出， 由此，把我们要求的问题简化成一个更小的子问题。子问题具有相同的求解方式，只不过是规模小了而已。最长上升子序列就符合这一特性。我们要求n个数的最长上升子序列，可以求前n-1个数的最长上升子序列，再跟第n个数进行判断。求前n-1个数的最长上升子序列，可以通过求前n-2个数的最长上升子序列……直到求前1个数的最长上升子序列，此时LIS当然为1。

　　让我们举个例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。

　　前1个数 d(1)=1 子序列为2；

　　前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7

　　前3个数 在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1

　　前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5

　　前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6

　　前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4

　　前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3

　　前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8

　　前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9

　　d(i)=max{d(1),d(2),……,d(i)} 我们可以看出这9个数的LIS为d(9)=5

　　总结一下，d(i)就是找以A[i]结尾的，在A[i]之前的最长上升子序列+1，当A[i]之前没有比A[i]更小的数时，d(i)=1。所有的d(i)里面最大的那个就是最长上升子序列。

        简单来说，每次都向前找比它小的数与比它大的数的位置，将第一个比它大的替换掉，这样虽然LIS序列的具体数字可能会变，但是很明显LIS长度还是不变的，因为只是把数替换掉了，并没有改变增加或者减少长度。

状态设计：F[i]代表以A[i]结尾的LIS的长度

状态转移：F[i]=max{F[j]+1}(1<=j< i,A[j]< A[i])

边界处理：F[i]=1(1<=i<=n)

时间复杂度：O(n^2)

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let max = 1;
    const dp = new Array(nums.length).fill(1);
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            nums[j] < nums[i] && (dp[i] = Math.max(dp[j] + 1, dp[i]));
        }
        max = Math.max(dp[i], max);
    }
    return max;
};

        这个算法的时间复杂度为〇(n²)，代码也清晰，但这并不是最优的算法。在限制条件苛刻的情况下，这种方法行不通。那么怎么办呢！有没有时间复杂度更小的算法呢？说到这里了，当然是有的啦！还有一种时间复杂度为〇(nlogn)的算法，下面就来看看。

---

方法二：二分+贪心

        新建一个low数组，里面的low[i]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然，其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护low数组，对于每一个a[i]，如果a[i] > low[当前最长的LIS长度]，就把a[i]接到当前最长的LIS后面，即low[++当前最长的LIS长度]=a[i]。
        那么，怎么维护low数组呢？
        对于每一个a[i]，如果a[i]能接到LIS后面，就接上去；否则，就用a[i]取更新low数组。具体方法是，在low数组中找到第一个大于等于a[i]的元素low[j]，用a[i]去更新low[j]。如果从头到尾扫一遍low数组的话，时间复杂度仍是O(n^2)。我们注意到low数组内部一定是单调不降的，所有我们可以二分low数组，找出第一个大于等于a[i]的元素。二分一次low数组的时间复杂度的O(lgn)，所以总的时间复杂度是O(nlogn)。

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    function binary_search(arr, l, r, key) {
    if (arr[r] < key)
        return r + 1;

    while (l < r) {
        let mid = l + Math.floor((r - l) / 2);
        if (arr[mid] < key)
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}
    let B = [nums[0]];
    for (let i = 1; i < nums.length; i++) {
        let item=B.at(-1);
        if(item < nums[i]) B.push(nums[i]);
        else if(nums[i]<item) {
            let next=binary_search(B,0,B.length-1,nums[i])
            B[next]=nums[i]
        };
    }
    return B.length;
};

---

方法三：dfs + 回溯

这个方法其实会稍微好理解些，比如此时的序列为：5,3,4,9,7

我们换种想法，我们的目标是为了能够得到最长的子序列，那么，假设我们能够得到所有的序列，在求得的同时进行剪枝操作，或许就能求出来，但我们不可避免的就是，时间复杂度会特别高：O（2^n），只做了解，因为特别扯淡，千万别在面试用哈哈！

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let res = 1;
    const dfs = (nums, path, index) => {
        res = Math.max(res, path.length);
        for (let i = index; i < nums.length; i++) {
            if (path.length > 0 && path[path.length - 1] >= nums[i]) {
                continue;
            }
            if ((path.length > 0 && path[path.length - 1] < nums[i]) || path.length === 0) {
                path.push(nums[i]);
            }
            dfs(nums, path, i + 1);
            path.pop();
        }
    }
    dfs(nums, [], 0);
    return res;
};

---

方法四：树状数组优化DP

        在方法一中，我们遇到一个问题就是，在动态规划数组的状态，每次都需要去遍历F函数前面的值，这会大大的增加我们的时间开销。我们可以借助数据结构来优化这个过程。用树状数组来维护F数组（据说分块也是可以的，但是分块是O(n*sqrt(n)）的时间复杂度，不如树状数组跑得快），每次都来获取到F数组中，第i个前面的数，大于F[i]的值，这样就能大大地提高我们的运行速度，代码如下：

/**
 * @param {number[]} nums
 * @return {number}
 */
// 实现树状数组
class FenwickTree {
    constructor(size) {
        this.size = size;
        this.tree = new Array(size + 1).fill(0);
    }
    // 更新
    update(index, delta) {
        for (; index <= this.size; index += index & -index) {
            this.tree[index] = Math.max(this.tree[index], delta);
        }
    }
    // 查询
    query(index) {
        let maxVal = 0;
        for (; index > 0; index -= index & -index) {
            maxVal = Math.max(maxVal, this.tree[index]);
        }
        return maxVal;
    }
}

var lengthOfLIS = function(nums) {
    // 去重，排序，并创建二维存索引
    const numToIndex = new Map([...new Set(nums)].sort((a, b) => a - b).map((num, index) => [num, index + 1]));
    const n = nums.length;
    const tree = new FenwickTree(numToIndex.size);
    let maxLen = 0;

    for (let i = 0; i < n; i++) {
        const index = numToIndex.get(nums[i]);
        const prevMax = tree.query(index-1);
        if(prevMax==0|| nums[i]!==nums[i-1]){
            const dpVal=prevMax+1
            tree.update(index, dpVal);
            maxLen = Math.max(maxLen, dpVal);
        }
    }
    return maxLen;
};

 值得一提的是：树状数组求LIS不去重的话就变成了最长不下降子序列了。

一个问题多解化，有时候有助于学习，题目往往会难在你是否发现此种类型的题。