300. Longest Increasing Subsequence

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.

方法一：暴力枚举

TC: O(2^n)
类似于subsets的思路，只不过在递归调用前需要判断是否符合递增的条件。
TLE ： 21/24 test cases passed

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> cur;
        maxLen = 1;
        for(int i=1; i<=nums.size(); ++i)
            dfs(nums, i, 0, cur);

        return maxLen;
    }
    
private:
    int maxLen;
    void dfs(vector<int>& nums, const int n, 
             int s, vector<int>& cur) {
        if(cur.size() == n) {
            maxLen = max(maxLen, n);
            return;
        }
        
        for(int i=s; i<nums.size(); ++i) {
            if(!cur.empty() && nums[i] <= cur.back())//在递归调用前需要判断是否符合递增的条件
                continue;
            cur.push_back(nums[i]);
            dfs(nums, n, i+1, cur);
            cur.pop_back();
        }
    }
};

方法二：记忆化递归

LIS([10,9,2,5,3,7,101,18]) = max {
LIS([10,9,2,5,3,7]) + 1,
LIS([10,9,2,5,3]) + 1,
LIS([10,9,2,5]) + 1,
LIS([10,9,2]) + 1,
LIS([10,9]) + 1,
LIS([10]) + 1
}

递归终止条件：
LIS([10,9,2]) = 1 //不存在比2小的数
LIS([10]) = 1 //单个元素

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;        
        f_ = vector<int>(n, 0);        
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans = max(ans, LIS(nums, i));
        return ans;
    }
private:
    vector<int> f_;
    // length of LIS ends with nums[r](必须使用nums[r])
    int LIS(const vector<int>& nums, int r) {
        if (r == 0) return 1;//单个元素nums[0]
        if (f_[r] > 0) return f_[r];
        int ans = 1;
        for(int i = 0; i < r; ++i)
            if (nums[r] > nums[i])
                ans = max(ans, LIS(nums, i) + 1);
        f_[r] = ans;
        return f_[r];
    }
};

方法三：动态规划

//f[i] : LIS which ends with nums[i], must use nums[i]
//f[i] = max(f[j]+1), j<i && nums[j]<nums[i]
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> f(nums.size(),1);
        for(int i=0; i<nums.size(); i++)
            for(int j=0; j<i; j++)
                if(nums[j] < nums[i])
                    f[i] = max(f[i],f[j]+1);
        return *max_element(f.cbegin(), f.cend());
    }
};

方法四：DP + Binary search

使用dp[i]保存所有长度为i+1的递增子序列中末尾元素的最小值。
注意最后v中存储的值并不一定是最长递增子序列，只是他们的长度相等。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> v;
        for(auto a : nums) {
            auto it = lower_bound(v.begin(), v.end(), a);
            if(it == v.end()) v.push_back(a);
            else *it = a;
        }
        return v.size();
    }
};

Follow up

求出所有最长的LIS数组：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<vector<int>> LIS(vector<int>& nums) {
        vector<int> cur;
        vector<vector<int>> ans;
        for(int i=0; i<=nums.size(); ++i)
            LIS(nums, i, 0, cur, ans);
        return ans;
    }

private:
    int maxLIS = 1;
    void LIS(const vector<int>& nums, const int n, int s,
            vector<int>& cur, vector<vector<int>>& ans) {
        if(cur.size() == n) {
            if(!ans.empty() && cur.size() > ans[0].size())
                ans.clear();//注意如果cur为长度更长的LIS，要先ans.clear()
            ans.push_back(cur);
            return;
        }


        for(int i=s; i<nums.size(); ++i) {
            if(!cur.empty() && nums[i] <= cur.back()) continue;
            cur.push_back(nums[i]);
            LIS(nums, n, i+1, cur, ans);
            cur.pop_back();
        }
    }
};

int main() {
    vector<int> nums{10, 9, 2, 5, 3, 7, 101, 18};
    vector<vector<int>> ans;
    ans = Solution().LIS(nums);
    for(auto num : ans){
        for(auto e : num)
            cout << e << " ";
        cout << endl;
    }
}

求最长递增子数组的个数

Lintcode 1093 最长升序子序列个数
仍然使用动态规划维护两个数组：
dp[i]表示以nums[i]为结尾的LIS的长度，用cnt[i]表示以nums[i]为结尾的最长LIS的个数。
遍历数组，对于nums[i], 再去遍历nums[j], 如果nums[i] <= nums[j], continue;
否则的话，更新dp[i]的规则不变;
更新cnt[i]的规则：
如果dp[j]+1==dp[i], cnt[i]+=cnt[j];//相当于最长LIS的长度没变，但是个数增加
如果dp[j]+1 > dp[i],则cnt[i] = cnt[j].//相当于最长LIS的长度变长了.

class Solution {
public:
    /**
     * @param nums: an array
     * @return: the number of longest increasing subsequence
     */
    int findNumberOfLIS(vector<int> &nums) {
        // Write your code here
        if(nums.empty()) return 0;
        const int n = nums.size();
        vector<int> dp(n,1);
        vector<int> ans(n,1);
        int max_ans = 1;
        
        for(int i=1; i<n; ++i) {
            for(int j=0; j<i; ++j) {
                if(nums[i] <= nums[j]) continue;
                else if(dp[j] + 1 > dp[i]) {//产生新的LIS
                    dp[i] = dp[j] + 1;
                    ans[i] = ans[j];
                }else if(dp[j] + 1 == dp[i])
                    ans[i] += ans[j];
            }
            max_ans = max(max_ans, dp[i]);
        }
        
        int cnt = 0;
        for(int i=0; i<n; ++i)
            if(dp[i]==max_ans)
                cnt += ans[i];
        return cnt;
    }
};

Longest Continuous Increasing Subsequence

这个相当于是连续递增的subarray.
本质上是一道动态规划的题目：
定义dp[i]为以num[i]结尾的最长连续递增子序列(LCIS), 要求num[i]必须使用。
状态转移方程：
if num[i] > num[i-1]:
dp[i] = dp[i-1] + 1
else
dp[i] = 1
最终答案存储在max(dp[i]), 0<=i<=n中。

可以降维，使用O(1)的空间；另外在循环的过程中就更新max_LCIS, 避免最后统一更新。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int cur = 1;
        int ans = 1;
        for(int i=1; i<nums.size(); ++i) {
            if(nums[i] > nums[i-1]) {
                cur++;
                ans = max(ans, cur);
            }else
                cur = 1;
        }
        return ans;
    }
};

最长递增子序列LIS