2407. Longest Increasing Subsequence II

2407. Longest Increasing Subsequence II
https://leetcode.com/problems/longest-increasing-subsequence-ii/

You are given an integer array nums and an integer k.

Find the longest subsequence of nums that meets the following requirements:
-> The subsequence is strictly increasing and
-> The difference between adjacent elements in the subsequence is at most k.

Return the length of the longest subsequence that meets the requirements.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.



Example 1:

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation:
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.

Example 2:

Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation:
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.

Example 3:

Input: nums = [1,5], k = 1
Output: 1
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.


Constraints:

1 <= nums.length <= 10^5
1 <= nums[i], k <= 10^5


---------------------------------------------------------------------------------------------------------------------------------------

BRUTE FORCE (TLE)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> dp(n,1);
        for(int end=1;end<n;end++){
            for(int start=0;start<end;start++){
                if(nums[end]>nums[start] && nums[end]-nums[start]<=k){
                    dp[end]=max(dp[end],dp[start]+1);
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};


--------------------------------------------------------------------------------------------------------------------------------------


SEGMENT TREE (AC)

class Solution {
private:
    const static int MAX=100001;
    int tree[4*MAX];
public:
    void update(int start, int end, int parent, int updateVal, int idx){
        if(start==end){
            tree[parent]=updateVal;
            return;
        }
        int mid=(start+end)/2;
        if(idx<=mid){
            update(start,mid,2*parent+1,updateVal,idx);
        }
        else{
            update(mid+1,end,2*parent+2,updateVal,idx);
        }
        tree[parent]=max(tree[2*parent+1],tree[2*parent+2]);
    }

    int maxLen(int start, int end, int l, int r, int parent){
        if(start>r || end<l){
            return 0;
        }
        if(start>=l && end<=r){
            return tree[parent];
        }
        int mid=(start+end)/2;
        int left=maxLen(start,mid,l,r,2*parent+1);
        int right=maxLen(mid+1,end,l,r,2*parent+2);
        return max(left,right);
    }

    int lengthOfLIS(vector<int>& nums, int k){
        memset(tree,0,sizeof(tree));
        int res=1;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==1){
                update(1,MAX,0,1,nums[i]); // because less than 1 not possible
                continue;
            }
            int best=maxLen(1,MAX,max(nums[i]-k,1),nums[i]-1,0)+1; // we are finding the best in range [max(1,nums[i]-k),nums[i]-1] and adding nums[i] to it
            update(1,MAX,0,best,nums[i]);  // update the best answer you got for nums[i]. Remember each element in this array is acting as an index in a segment tree
            res=max(res,best);
        }
        return res;
    }
};