Efficient O(nlogn) solution using Binary Search and DP

longest_increasing_subseq.cpp

//Function to find length of longest increasing subsequence.
  // O(nlogn) solution using Binary Search + DP
  int longestSubsequence(int n, int arr[]) {
      // your code here
      /*
          Notation:
          1) ith index means length of increasing subseq = i
          2) ith index will contain the smallest ending element of the LIS of length i
      */
      vector<int> dp(n + 1, INT_MAX);
      dp[0] = INT_MIN; // facilitates upper_bound function

      for(int i = 0; i < n; i++) {
          int idx = upper_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
          // condition check: we store the smaller element at the same index (collision of 2 values)
          if(arr[i] > dp[idx - 1] && arr[i] < dp[idx])
              dp[idx] = arr[i];
      }
      // find the first index from right having value != INT_MAX
      for(int i = n; i >= 0; i--) {
          if(dp[i] != INT_MAX)
              return i;
      }
  }