DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Maximum Multiplication Score

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)