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)