clueless coding // TODO: be smarter

LeetCode Longest Increasing Subsequence: CPP Solution



TL;DR Code Solution


int lengthOfLIS(vector<int>& nums) {

    vector<int> result;

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

        if (i == 0 || nums[i] > result.back()) {
            result.push_back(nums[i]);
        }
        else {
            int left = 0;
            int right = result.size() - 1;
            while (left <= right) {
                int middle = (left + right) / 2;

                if (result[middle] < nums[i]) {
                    left = middle + 1;    
                }
                else {
                    right = middle - 1;
                }
            }
            result[left] = nums[i];
        }
    }


    return result.size();

}