Longest Increasing Subsequence - Amazon Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp;  // dp[i] = last digit in the list of size i+1, dp is increasing
    for (int& i : nums) {
        if (dp.empty()) {
            dp.push_back(i);
            continue;
        }
        auto it = lower_bound(dp.begin(), dp.end(), i);
        if (it == dp.end())
            dp.push_back(i);
        else {
            int idx = it - dp.begin();
            dp[idx] = i;
        }
    }
    return dp.size();
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums):
        if not nums:
            return 0

        def get_index(arr, target):
            l, r = 0, len(arr) - 1
            res = r + 1
            while l <= r:
                mid = (l + r) // 2
                if target < arr[mid]:
                    res = mid
                    r = mid - 1
                elif target > arr[mid]:
                    l = mid + 1
                else:
                    return mid
            return res

        dp = []
        res = 0
        for num in nums:
            idx = get_index(dp, num)
            if idx == res:
                dp.append(num)
                res += 1
            else:
                dp[idx] = num

        return res