Skip to content

LongestIncreasingSubsequence.md

Latest commit

 

History

History
126 lines (112 loc) · 3.5 KB

LongestIncreasingSubsequence.md

File metadata and controls

126 lines (112 loc) · 3.5 KB

Longest Increasing Subsequence:

1. Recursion:

public int Lis(int[] nums,int index,int prev){
       if(index==nums.length){
           return 0;
       }
       int take=0;
       int notTake=0;
       if(prev==-1 || nums[index]>nums[prev]){
           take=Lis(nums,index+1,index)+1;
       }
       notTake=Lis(nums,index+1,prev);
       return Math.max(take,notTake);
   }

Time: O(2^n) Space: O(n). wefwefwe

2. Memoization:

since there are recuring sub problems we store the subproblems in the dp matrix, with index and prev as it's co-ordinate.

class Solution {
    int[][] dp;
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        dp=new int[n+1][n+1];
        return Lis(nums,0,-1);
    }

    public int Lis(int[] nums,int index,int prev){
        if(index==nums.length) {
            return 0;
        }
        int take=0;
        int notTake=0;
        if(prev==-1 || nums[index]>nums[prev]){
            if(dp[index+1][index+1]==0) {
                dp[index+1][index+1]=Lis(nums,index+1,index);
            }
            take=dp[index+1][index+1]+1;
        }
        // if the subproblems doesn't exist, then fint it's value
        if(dp[index+1][prev+1]==0){
            dp[index+1][prev+1]=Lis(nums,index+1,prev);
        }
        
        notTake=dp[index+1][prev+1];
        return Math.max(take,notTake);

    }
}

Time: O(n^2) Space: n*n (dp matrix) + n(recursive stack)

3. Tabulation:

Step to convert memoization to tabulation 1. write the base case 2. write the changing parameters (in this case index and prev) Iterate index from n-1 --> 0 and prev from index-1 --> -1 3. copy the recurrence

//recurrence
		if(prev==-1 || nums[index]>nums[prev]){
            take=Lis(nums,index+1,index)+1;
        }
        notTake=Lis(nums,index+1,prev);

Just change the Lis(index+1,prev) to dp[index+1][prev+1] the +1 in the second co-ordinate int the dp is due to the fact the prev can be -1 but index can't so we shift the coordinate by 1.

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int[][] dp=new int[n+1][n+1];
        for(int index=n-1;index>-1;index--){
            for(int prev=index-1;prev>=-1;prev--){
                int take=0;
                int notTake=0;
                if(prev==-1 || nums[index]>nums[prev]){
                    take=dp[index+1][index+1]+1;
                }
                notTake=dp[index+1][prev+1];
                dp[index][prev+1]=Math.max(take,notTake);
            }
        }
        return dp[0][0];
    }
}

Time: O(n^2) Space: (n*n)

4. Tabulation with space optimization

In the above code we can see that at every iteration we are dealing with index+1 and index we can space optimise it by using two array instead of matrix and can convert dp[index+1][somethinng] to next[something] and dp[index][something] to curr[something]

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int[] next=new int[n+1];
        int[] curr=new int[n+1];
        for(int index=n-1;index>-1;index--){
            for(int prev=index-1;prev>=-1;prev--){
                int take=0;
                int notTake=0;
                if(prev==-1 || nums[index]>nums[prev]){
                    take=next[index+1]+1;
                }
                notTake=next[prev+1];
                curr[prev+1]=Math.max(take,notTake);
            }
            next=curr;
        }
        return curr[0];
    }
}