Problem
TC: O(4*m) = O(m)
SC: O(4*m) = O(m) ( dp array) + O(4+m) for recursive stack space
class Solution { public long maxScore(int[] a, int[] b) { long dp[][] = new long[a.length][b.length]; for(long d[] : dp) Arrays.fill(d,-1); return max(0,0,a,b,dp); } public long max(int i, int j, int a[], int b[],long dp[][]){ //base case if(i ==a.length) return 0; if(j ==b.length) return Long.MIN_VALUE/2; if(dp[i][j]!=-1) return dp[i][j]; long take = (long)a[i]*b[j] + max(i+1,j+1,a,b,dp); long dontTake = (long) max(i,j+1,a,b,dp); return dp[i][j] = Math.max(take,dontTake); } } 
Top comments (0)