DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Longest increasing subsequence

Problem

class Solution {
    // Function to find length of longest increasing subsequence.
    static int longestSubsequence(int n, int a[]) {
        // tabulation method (bottom up ) 
        int dp[][] = new int[a.length+1][a.length+1];
        for(int index = a.length-1;index>=0;index--){
            for(int prev = a.length-1;prev>=-1;prev--){
                int take  = 0;
                if(prev ==-1 || a[prev] < a[index]){
                    take = Integer.max(take , 1 + dp[index+1][index+1]);
                }
                int dontTake  = dp[index+1][prev+1];
                dp[index][prev+1] = Integer.max(take,dontTake);
            }
        }
        return dp[0][0];
    }

//memoization method (top down) 
    public static int count(int index, int prev, int arr[], int dp[][]){
        //base case
        if(index ==arr.length) return 0;
        if(dp[index][prev+1]!=-1) return dp[index][prev+1];
        int take  = 0;
        if(prev ==-1 || arr[prev] < arr[index]){
            take = Integer.max(take , 1 + count(index+1,index,arr,dp));
        }
        int dontTake  = count(index+1,prev,arr,dp);
        return dp[index][prev+1] = Integer.max(take,dontTake);
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)