# Longest Increasing Subsequence

There are two method to get the longest increasing subsequence, the first one it use the Dynamic Programming, which has the O(n*n) complexity; the other one is using the greedy algorithm, which can decrease the complexity into O(nlgn).

## Dynamic Programming

## Greedy

In the following code, if we get the number that is bigger than the current LIS array.back(), we will add the element. Else, we will use the upper bound to find the right position to replace the value.

Current LIS = [1, 4, 6], new element = 5

Then, the new LIS = [1, 4, 5], which will give the further element such as 6 to put into the LIS array. There are two types of LIS: Longest Increasing Subsequence, and Longest Non-Decreasing Subsequence.

// Longest non-decreasing subsequence
int LNDS(vector<int> &v){
    vector<int> q;
    for(auto x:v){
        if(q.size() == 0 || q.back() <= x){
            q.push_back(x);
        }
        else{
            auto it = upper_bound(q.begin(), q.end(), x);
            *it = x;
        }
    }
    return q.size();
}

// Longest increasing subsequence
int LIS(vector<int> &v){
    vector<int> q;
    for(auto x:v){
        if(q.size() == 0 || q.back() < x){
            q.push_back(x);
        }
        else{
            auto it = lower_bound(q.begin(), q.end(), x);
            *it = x;
        }
    }
    return q.size();
}

## [300.Longest-Increasing-Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)
### Problem:
Find the LIS of an array.
### Solution:
Use the same code above.

## [354.Russian-Doll-Envelopes](https://leetcode.com/problems/russian-doll-envelopes/)
### Problem:
You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 
([2,3] => [5,4] => [6,7]).

### Solution:

First sort with the height with increasing order, and sort width with decreasing order. Therefore, if you get one evelope in height h, width w, then you will not get another width w' that is bigger than w, which has the same height. Therefore, we can pick the LIS based on the width array.

class Solution {
    static bool cmp(vector<int> &a, vector<int> &b){
        if(a[0] == b[0]) return a[1] > b[1];
        return a[0] < b[0];
    }
public:
    int maxEnvelopes(vector<vector<int>>& e) {
        sort(e.begin(), e.end(), cmp);
        vector<int> arr;
        for(auto n:e){
            if(arr.size() == 0 || n[1] > arr.back()){
                arr.push_back(n[1]);
            }
            else{
                auto it = lower_bound(arr.begin(), arr.end(), n[1]);
                *it = n[1];
            }
        }
        return arr.size();
    }
};

## [1713.Minimum-Operations-to-Make-a-Subsequence ](https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/)

### Problem
You are given an array target that consists of **distinct integers** and another integer array arr that can have duplicates.

In one operation, you can insert any integer at any position in arr. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.

Return the minimum number of operations needed to make target a subsequence of arr.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: You can add 5 and 1 in such a way that makes arr = [5,9,4,1,2,3,4], then target will be a subsequence of arr.

### Solution

This is the Longest Common Subsequence problem; however, the complexity of LCS will be O(n*m). Therefore, if the n and m is larger than 1e5, then you will get TLE result. Therefore, we need to know that the LCS problem can be reduced to LIS problem if and only if the number of the target array that consists of **distinct integers**.

Therefore, since the target array has all distinct integers, we can label the integer with their index, and use those mapping index to replace the integer in the arr array. Therefore, the problem can be finding the LIS in the mapped array which only consist the value that is appear in target array.

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> mp;
        for(int i = 0; i < target.size(); ++i){
            mp[target[i]] = i;
        }
        vector<int> nums;
        for(int i = 0; i < arr.size(); ++i){
            if(mp.find(arr[i]) == mp.end()) continue;
            nums.push_back(mp[arr[i]]);
        }
        vector<int> q;
        for(auto x:nums){
            if(q.size() == 0 || q.back() < x){
                q.push_back(x);
            }
            else{
                auto it = lower_bound(q.begin(), q.end(), x);
                *it = x;
            }
        }
        return target.size()-q.size();
    }
};

## [1964.Find-the-Longest-Valid-Obstacle-Course-at-Each-Position](https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/)
### Problem
You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the ith obstacle.

For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:

You choose any number of obstacles between 0 and i inclusive.
You must include the ith obstacle in the course.
You must put the chosen obstacles in the same order as they appear in obstacles.
Every obstacle (except the first) is taller than or the same height as the obstacle immediately before it.
Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.

Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [1], [1] has length 1.
- i = 1: [1,2], [1,2] has length 2.
- i = 2: [1,2,3], [1,2,3] has length 3.
- i = 3: [1,2,3,2], [1,2,2] has length 3.

### Solution

Simply, the problem asks us to find the LIS from obstacles[0:i], where i = 1 to n. Therefore, we can store the length of LIS when we construct the LIS array.

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        vector<int> arr;
        vector<int> res;
        for(auto n:obstacles){
            if(arr.size() == 0 || n >= arr.back()){
                arr.push_back(n);
                res.push_back(arr.size());
            }
            else{
                auto it = upper_bound(arr.begin(), arr.end(), n);
                res.push_back(it-arr.begin()+1);
                *it = n;
            }
        }
        return res;
    }
};

## [2111.Minimum-Operations-to-Make-the-Array-K-Increasing ](https://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/)

### Problem
You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k.

The array arr is called K-increasing if arr[i-k] <= arr[i] holds for every index i, where k <= i <= n-1.

For example, arr = [4, 1, 5, 2, 6, 2] is K-increasing for k = 2 because:

    arr[0] <= arr[2] (4 <= 5)
    arr[1] <= arr[3] (1 <= 2)
    arr[2] <= arr[4] (5 <= 6)
    arr[3] <= arr[5] (2 <= 2)

However, the same arr is not K-increasing for k = 1 (because arr[0] > arr[1]) or k = 3 (because arr[0] > arr[3]).
In one operation, you can choose an index i and change arr[i] into any positive integer.

Return the minimum number of operations required to make the array K-increasing for the given k.

### Solution

The problem is asking us to find LIS from different sequence as follow:

s1: 0, 0+k, 0+2k, 0+3k, ...
s2: 1, 1+k, 1+2k, 1+3k, ...
...
sk-1: k-1, k-1+k, k-1+2k, ...

Therefore, we need to first construct those array, and use the LIS algorithm we mentioned before. Then, we will get the answer.

class Solution {
public:
    int LIS(vector<int> &v){
        vector<int> q;
        for(auto x:v){
            if(q.size() == 0 || q.back() <= x){
                q.push_back(x);
            }
            else{
                auto it = upper_bound(q.begin(), q.end(), x);
                *it = x;
            }
        }
        return q.size();
    }
    int kIncreasing(vector<int>& arr, int k) {
        int n = arr.size(), res = 0;
        for(int t = 0; t < k; ++t){
            vector<int> nums;
            for(int i = t; i < n; i+=k){
                nums.push_back(arr[i]);
            }
            res += nums.size()-LIS(nums);
        }
        return res;
    }
};