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();

    }

};