Q43 Longest Increasing Subsequence - LeetCode 300

class Solution {
    public int lengthOfLIS(int[] nums) {
        /* LIS in O(nlogn) -> shorturl.at/tyJZ7
        
        we make a dp array of length n where every cell denote the last element
        of ith length LIS , we make an upperbound function which returns the 
        just greater or equal to target index where we keep updating the values
        if we encounter another smaller value than previously stored at index

        we do this so that we can make a longer LIS in the future , in the end 
        we traverse reversely and at any index if we find value other than INTMAX
        we return that index + 1 which denotes length of MAX LIS;
        */

        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp , Integer.MAX_VALUE);

        //traverse the array use upperbound function to update values
        for(int i = 0 ; i < n ; i++){
            int idx = upperBound(dp , 0 , i ,nums[i]);
            dp[idx] = nums[i];           
        }

        //traverse reversely to find the max LIS 
        for(int i = n-1 ; i>=0 ; i--){
            if(dp[i] != Integer.MAX_VALUE)
            return i+1;
        }

        return -1;  //will never reach this statement
    }

    //upperbound returns just greater or equal to value index for updating value
    public int upperBound(int[] dp , int low , int high , int target){

        while(low <= high){
            int mid = low + (high - low)/2;

            if(dp[mid] == target) 
            return mid;
            
            else if(dp[mid] > target)
            high = mid-1;

            else
            low = mid+1;
        }

        return low;
    }

    //using n+1 as we cant store -1 as index therefore we shift it by 1
     //Recursion->exponential Memo-> n*n+1
    public int solve(int[] nums , int i , int prev , Integer[][] dp){
        if(i == nums.length ) return 0;

        if(dp[i][prev+1] != null)
        return dp[i][prev+1];
        
        int len = 0 + solve(nums , i+1 , prev,dp);

        if(prev == -1 || nums[i] > nums[prev])
        len = Math.max(len , 1+ solve(nums , i+1 , i,dp));

        return dp[i][prev+1] = len;
    }
}