Longest Increasing Subsequence & Path Print (LIS)

class Solution {

public:

    int lengthOfLIS(vector<int>& nums) {

        int n = nums.size();

        vector<int> sub, subIndex; 

        vector<int> path(n, -1); 

        for (int i = 0; i < n; ++i) {

            if (sub.empty() || sub[sub.size() - 1] < nums[i]) {

                path[i] = sub.empty() ? -1 : subIndex[sub.size() - 1];

                sub.push_back(nums[i]);

                subIndex.push_back(i);

            } else {

                int idx = lower_bound(sub.begin(), sub.end(), nums[i]) - sub.begin();

                path[i] = idx == 0 ? -1 : subIndex[idx - 1];

                sub[idx] = nums[i];

                subIndex[idx] = i;

            }

        }

        vector<int> ans;

        int t = subIndex[subIndex.size() - 1];

        while (t != -1) {

            ans.push_back(nums[t]);

            t = path[t];

        }

        reverse(ans.begin(), ans.end());

        for(int i=0;i<ans.size();i++){

            cout<<ans[i]<<" ";

        }

        cout<<endl;

        return ans.size();

    }

};

Longest non-decreasing subsequence - TC: O(nlogn)

int longestNonDecresingSubsequenceLength(vector<int> a) {

    vector<int> s;

    s.push_back(a[0]);

    int n = a.size();

    int len = 1;

    for (int i = 1; i < n; i++) {

        int idx = upper_bound(s.begin(), s.end(), a[i]) - s.begin();

        int m = s.size();

        if (m > idx) {

            s[idx] = a[i];

        } else {

            s.push_back(a[i]);

        }

    }

    return s.size();

}