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);
}
}
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)