
```
int lengthOfLIS(vector<int>& nums) {
    vector<int> res;
    for(int i=0; i<nums.size(); i++) {
        auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
        if(it==res.end()) res.push_back(nums[i]);
        else *it = nums[i];
    }
    return res.size();
}
```
### The algo is O(nlogn) because lower_bound() is logarithmic on a sorted input.
We keep our vector res sorted, so the search in dp is logarithmic.

## Res is composed to be:

1. sorted

2. having a length of the longest found increasing sub-sequence. So it doesn't contain that subsequence. Only it's length is valid.

## So what algo is doing? For each number we have 2 options:
- if it's the highest found value, we push it back, since a high value obviously makes our increasing sequence longer

- if it's not the highest found value, then it could be a nice start (or continuation) of a shorter sequence. And we keep that sequence in place. Merging all found and possible sequences into one dp

See how res is changing when we go through the numbers:

[1,2,7,8,3,4,5,9,0]

1 -> [1]

2 -> [1,2]

7 -> [1,2,7]

8 -> [1,2,7,8]

3 -> [1,2,3,8]  // we replaced 7 with 3, since for the longest sequence we need only the last number and 1,2,3 is our new shorter sequence

4 -> [1,2,3,4] // we replaced 8 with 4, since the max len is the same but 4 has more chances for longer sequence

5 -> [1,2,3,4,5]

9 -> [1,2,3,4,5,9]

0 -> [0,2,3,4,5,9] // we replaced 1 with 0, so that it can become a new sequence

So in the end our res contains [0,2,3,4,5,9] which is not a found sequence, but it has the length of the valid answer = 6.

Longest Increasing subsequence

```
If input array is sorted then
    - Binary search
    - Two pointers

If asked for all permutations/subsets then
    - Backtracking

If given a tree then
    - DFS
    - BFS

If given a graph then
    - DFS
    - BFS

If given a linked list then
    - Two pointers

If recursion is banned then
    - Stack

If must solve in-place then
    - Swap corresponding values
    - Store one or more different values in the same pointer

If asked for maximum/minumum subarray/subset/options then
    - Dynamic programming

If asked for top/least K items then
    - Heap

If asked for common strings then
    - Map
    - Trie

Else
    - Map/Set for O(1) time & O(n) space
    - Sort input for O(nlogn) time and O(1) space
```

Common patterns for DSA problems

*  lis (longest increasing subsequences) and lds ( longest decreasing subsequence) are two dp arrays, both filled in similar fashion (read comments).
*  similar problem - longest bitonic subsequence
*  **Complexity Analysis**
Time: O(n^2)
Space: O(n)

```
class Solution
{
public:
  int minimumMountainRemovals(vector<int> &nums)
  {
    int n = nums.size();
      
    //lis[i] stores the longest increasing subsequences ending at i
    vector<int> lis(n, 1);

    for (int i = 0; i < n; i++)
    {
      int maxi = 1;
      for (int j = 0; j < i; j++)
      {
        if (nums[j] < nums[i])
        {
          maxi = max(maxi, lis[j] + 1);
        }
      }
      lis[i] = maxi;
    }

    // now apply above algorithm in reverse
    //lds[i] stores the longest increasing subsequences till i in the reverse of array nums
    //OR
    //lds[i] stores longest decreasing subsequence starting from i
    vector<int> lds(n, 1);
    for (int i = n - 1; i >= 0; i--)
    {
      int maxi = 1;
      for (int j = i + 1; j < n; j++)
      {
        if (nums[i] > nums[j])
        {
          maxi = max(maxi, lds[j] + 1);
        }
      }
      lds[i] = maxi;
    }

    /*Add lds[i] and lis[i] but nums[i] is counted twice so longest bitonic subsequence lis[i] + lds[i] - 1
		*/
    int lbs = 0;
    for (int i = 0; i < n; i++)
    {
      if (lis[i] > 1 && lds[i] > 1)
        lbs = max(lis[i] + lds[i] - 1, lbs);
    }
    //remove other elements which are not in subsequence
    return n - lbs;
  }
};
```


Solution: Leetcode#1671 Minimum Number of Removals to Make Mountain Array

In the solution t_ik1 represent--profit at the end of the ith day with max no. of transactions=k and no. of stocks in hand = 1
```
class Solution
{
public:
    int maxProfit(int k, vector<int> &prices)
    {
        //optimization part - min it takes atleast two days to complete a transaction
so answer does not depend on value of k
        if (k >= prices.size() >> 1)
        {
            int t_ik0 = 0, t_ik1 = INT_MIN;

            for (int price : prices)
            {
                int t_ik0_old = t_ik0;
                t_ik0 = max(t_ik0, t_ik1 + price);
                t_ik1 = max(t_ik1, t_ik0_old - price);
            }

            return t_ik0;
        }
        vector<int> t_ik0(k + 1);
        vector<int> t_ik1(k + 1, INT_MIN);
        for (int price : prices)
        {
            for (int j = k; j > 0; j--)
            {
                t_ik0[j] = max(t_ik0[j], t_ik1[j] + price);
                t_ik1[j] = max(t_ik1[j], t_ik0[j - 1] - price);
            }
        }

        return t_ik0[k];
    }
};

Solution: Leetcode#188. Best Time to Buy and Sell Stock IV

```
class Solution {
    const int mod=1e9+7;
public:
    /*dp[n]=dp[n-1]+dp[n-2]+ 2*(dp[n-3]+...+d[0])
=dp[n-1]+dp[n-2]+dp[n-3]+dp[n-3]+2*(dp[n-4]+...+d[0])
=dp[n-1]+dp[n-3]+(dp[n-2]+dp[n-3]+2*(dp[n-4]+...+d[0]))
=dp[n-1]+dp[n-3]+dp[n-1]
=2*dp[n-1]+dp[n-3]*/
    int numTilings(int n) {
        vector<int> dp(n+1);
        if(n==1)
            return 1;
        else if(n==2)
            return 2;
        else if(n==3)
            return 5;
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        dp[3]=5;
        for(int i=4;i<=n;i++)
        {
            dp[i]+=((long)dp[i-1]*2+(long)dp[i-3])%mod;
        }
        return dp[n];
    }
};

Solution: Leetcode#790. Domino and Tromino Tiling

Sliding Window Template

```
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int b=0,e=0;
        int n=A.size();
        int counter=K;
        int maxl=0;
        while(e<n)
        {
            if(A[e]==0)
                counter--;
            e++;
            while(counter<0&&b<n)
            {
                if(A[b]==0)
                    counter++;
                b++;   
            }
            maxl=max(maxl, e-b);        
        }
        return maxl;
    }
};
```

Longest Increasing subsequence

Common patterns for DSA problems

Solution: Leetcode#1671 Minimum Number of Removals to Make Mountain Array

Solution: Leetcode#188. Best Time to Buy and Sell Stock IV

Solution: Leetcode#790. Domino and Tromino Tiling

Solution: Leetcode#1004. Max Consecutive Ones III