Longest increasing subsequence DP solution

#1

hi i am struggling with longest increasing subsequence problem i have figured out the recursive solution and its working but i am unable to apply top down dp to this problem kindly help My code is here:

MAIN : -
int dp[] = new int[arr.length];

	 System.out.println(LIS(arr,0,Integer.MIN_VALUE,"",dp));

Method Called:

private static int LIS(int[] arr, int i,int prev,String str,int[] dp) {
if(i==arr.length) {
System.out.println(str);
return 0;
}
int ans = 0;
if(dp[i]!=0) return dp[i];
if(arr[i] > prev)
ans = Math.max(ans,LIS(arr, i+1,arr[i],str+arr[i],dp)+1);
ans = Math.max(ans,LIS(arr, i+1, prev,str,dp));
dp[i] = ans;
return dp[i];
}
Kindly highlight my mistake and help with the solution for same

#2

hi @rdsaurabh97
Recursive approach to solve LIS length in java would be like below -

public int LIS(int[] arr) {
return LISLength(arr, Integer.MIN_VALUE, 0);
}

public int LISLength(int[] arr, int prev, int current) {
    if (current == arr.length) {
        return 0;
    }
    int include = 0;
    if (arr[current] > prev) {
        include = 1 + LISLength(arr, arr[current], current + 1);
    }
    int exclude = LISLength(arr, prev, current + 1);
    return Math.max(include, exclude);
}

But it would work with O(2^n) time complexity so we need to use memoization technique to reduce the complexity with below approach -

public int LIS(int[] arr) {
int memoTable[][] = new int[arr.length + 1][arr.length];
for (int[] l : memoTable) {
Arrays.fill(l, -1);
}
return LISLength(arr, -1, 0, memoTable);
}
public int LISLength(int[] arr, int prev, int current, int[][] memoTable) {
if (current == arr.length) {
return 0;
}
if (memoTable[prev + 1][current] >= 0) {
return memoTable[prev + 1][current];
}
int include = 0;
if (prev < 0 || arr[current] > arr[prev]) {
include = 1 + LISLength(arr, current, current + 1, memoTable);
}

    int exclude = LISLength(arr, prev, current + 1, memoTable);
    memoTable[prev + 1][current] = Math.max(include, exclude);
    return memoTable[prev + 1][current];
}

So O(n^2) would be optimized time complexity with memoization technique.

#3

@rdsaurabh97
mark your doubt as resolved and rate me aswell

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.