classSolution{// Function to find length of longest increasing subsequence.staticintlongestSubsequence(intn,inta[]){// tabulation method (bottom up ) intdp[][]=newint[a.length+1][a.length+1];for(intindex=a.length-1;index>=0;index--){for(intprev=a.length-1;prev>=-1;prev--){inttake=0;if(prev==-1||a[prev]<a[index]){take=Integer.max(take,1+dp[index+1][index+1]);}intdontTake=dp[index+1][prev+1];dp[index][prev+1]=Integer.max(take,dontTake);}}returndp[0][0];}//memoization method (top down) publicstaticintcount(intindex,intprev,intarr[],intdp[][]){//base caseif(index==arr.length)return0;if(dp[index][prev+1]!=-1)returndp[index][prev+1];inttake=0;if(prev==-1||arr[prev]<arr[index]){take=Integer.max(take,1+count(index+1,index,arr,dp));}intdontTake=count(index+1,prev,arr,dp);returndp[index][prev+1]=Integer.max(take,dontTake);}}
Top comments (0)
Subscribe
We're a place where coders share, stay up-to-date and grow their careers.
Top comments (0)