300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?

S1: 坐标型DP O($$n^2$$)

状态: LIS[i]存储以nums[i]结尾的LIS的元素个数

方程: 对任意i<j如果nums[i]<nums[j],他们可组成IS，LIS[j] = max(LIS[j], LIS[i] + 1)

初始化: LIS初始化为1即只有自己存在于IS

答案: LIS数组中最大的值

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int result = 0;
        vector<int> LIS(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[j] > nums[i]) {
                    LIS[j] = max(LIS[j], LIS[i] + 1);
                }
            }
        }
        for (auto i: LIS) {
            result = max(result, i);
        }
        return result;
    }

Longest Increasing Continuous Subsequence

Give an integer array，find the longest increasing continuous subsequence in this array.

An increasing continuous subsequence:

• Can be from right to left or from left to right.
• Indices of the integers in the subsequence should be continuous.

S: 左右两遍DP

    int longestIncreasingContinuousSubsequence(vector<int>& A) {
        int result = 0;
        int curLen = 1;
        for (int i = 1; i < A.size(); ++i) {
            if (A[i] > A[i-1]) {
                curLen++;
                result = max(result, curLen);
            } else {
                curLen = 1;
            }
        }
        curLen = 1;
        for (int i = A.size() - 2; i >= 0; --i) {
            if (A[i] > A[i + 1]) {
                curLen++;
                result = max(result, curLen);
            } else {
                curLen = 1;
            }
        }
        return result;
    }

Longest Increasing Continuous subsequence II

Give you an integer matrix (with row size n, column size m)，find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).

S: 记忆化搜索，剪支 O(mn)

len[i][j]存储以A[i][j]开始的lics的长度，碰到计算过的len[i][j]直接返回

class Solution {
public:
    int longestIncreasingContinuousSubsequenceII(vector<vector<int>>& A) {
        int m = A.size();
        if (m == 0) {
            return 0;
        }
        int n = A[0].size();
        len = vector<vector<int>>(m, vector<int>(n, -1));
        int maxlen = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                maxlen = max (dfs(A, i, j), maxlen);
            }
        }
        return maxlen;
    }

    int dfs(vector<vector<int>>& A, int i, int j) {
        if (len[i][j] != -1) {
            return len[i][j];
        }
        int m = A.size();
        int n = A[0].size();
        int maxLen = 0;
        vector<int> dx{0, 1, 0, -1};
        vector<int> dy{1, 0, -1, 0};
        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && A[x][y] > A[i][j]) {
                maxLen = max(dfs(A, x, y), maxLen);
            }
        }
        maxLen++;
        len[i][j] = maxLen;
        return maxLen;
    }
private:
    vector<vector<int>> len;
};

334. Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given[1, 2, 3, 4, 5],
returntrue.

Given[5, 4, 3, 2, 1],
returnfalse.

S: DP / trick O(n)

因为只需要求三元组的存在，可以用两个变量first,second存储三元组中递增的前两个数的candidate，只要碰到比这两个数大的第三个数就返回true. 即使first更新后出现在second之后也不影响结果，只要之前满足条件的first出现过即可。

    bool increasingTriplet(vector<int>& nums) {
        if (nums.size() < 3) {
            return false;
        }
        int first = INT_MAX;
        int second = INT_MAX;
        for (int i : nums) {
            if (i <= first) {
                first = i;
            } else if (i <= second) {
                second = i;
            } else {
                return true;
            }
        }
        return false;
    }

354. Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers(w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:
Given envelopes =[[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is3([2,3] => [5,4] => [6,7]).

S: DP O(n^2)

按w排序后用dp找longest increasing subsequence

    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        int n = envelopes.size();
        if (n == 0) return 0;
        sort(envelopes.begin(), envelopes.end());
        vector<int> dp(n, 1);
        int result = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            result = max(result, dp[i]);
        }
        return result;
    }