[LeetCode | C++] July LeetCoding Challenge 2021 — Week2 Longest Increasing Subsequence (9th,July)

📃 Problem

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3808/

💡 Check Point

1. Determine how to get the longest increasing subsequence of array[:i]
2. Determine which value is the maximum subsequence size into an array

👩‍💻 My Solution

1. Using DP

int lengthOfLIS(vector<int>& nums) {
     int* dp = new int[nums.size()];
     for(int i = 0; i <  nums.size(); i++) {
         dp[i] = 1;
     }
     int maxValue = 1;
     for(int i = 1; i < nums.size(); i++) {
         for(int j = 0; j < i; j++) {
             if(nums[i] > nums[j] && dp[i] < dp[j]+1) {
                dp[i] = dp[j] + 1;
                maxValue = max(dp[i], maxValue);
              }
          }
      }
     return maxValue;
}

2. Using Binary Search

int lengthOfLIS(vector<int>& nums) {
     vector<int> v;
     v.push_back(-__INT_MAX__);
     for(int i = 0; i < nums.size(); i++) {
         if(v.back() < nums[i]) {
            v.push_back(nums[i]);
          } else {
              auto it = lower_bound(v.begin(), v.end(), nums[i]);
              *it = nums[i];
          }
     }
     return v.size()-1;
}