CODEWITHSUNDEEP
algorithmdynamic-programming
Arat254
Arat254

Reputation: 469

How to convert the following recurrence to top down dynamic programming?

I am trying to solve the Maximum Product Subarray problem from leetcode.

The problem description is: Given an integer array, find the contiguous subarray within the array containing at least one number which has the largest product.

Example: Input: [2,3,-2,4], Output: 6

To solve this I am using the following logic: let f(p,n) output the correct result until index n of the array where the result is p. So the recurrence is:

f(p,n) = p // if(n=a.length)
f(p,n) = max( p, f(p*a[n], n+1), f(a[n], n+1) ) // otherwise

This works for regular recursion (code below).

private int f(int[] a, int p, int n) {
    if(n==a.length)
        return p;
    else
        return max(p, f(a, p*a[n], n+1), f(a, a[n], n+1));
}

However I am having trouble converting it to top-down dynamic programming. The approach I have been using to convert a recursive program into one that uses top-down DP is:

This is a general approach that I have been using and it has worked for most of the dp problems I have done however it does not work for this problem.

The (incorrect) code using this approach is shown below:

private int f(int[] a, int p, int n, int[] dp) {
    if(dp[n]!=0)
        return dp[n];
    if(n==a.length)
        dp[n] = p;
    else
        dp[n] = max(p, f_m(a, p*a[n], n+1, dp), f_m(a, a[n], n+1, dp));
    return dp[n];
}

I call the functions from the main function as follows:

// int x = f(a, a[0], 1, dp); - for incorrect top-down dp attempt
// int x = f(a, a[0], 1); - for regular recursion

An example where it does not work is: [3,-1,4]. Here it incorrectly outputs 3 instead of 4.

From what I understand, the problem is because both subproblems refer to the same n+1 index of the DP array so only 1 subproblem is solved which results in the incorrect answer.

So my question is:

How can I convert this recurrence to a top-down DP program? Is there a general approach that I can follow for cases like this?

Upvotes: 0

Views: 506

Answers (2)

Saurabh Yadav
Saurabh Yadav

Reputation: 1

You can do it the way you are trying but , I will suggest you an easy way to the problem Its o(n) and doesn't even require to store the array thus o(1) space.

Let us keep 2 variables min and max. which stores the minimum and the maximum product so far , we are keeping min marker due to -ve numbers as two negative numbers can product to large number.

rest is easy,

initialise min=1 and max=1 and ans=0(as qs says atleast one number needs to be there you can change this initialisation accordingly) i.e the first element.

start reading the input one element at a time say 'a' loop over length of the array

{

if(a>0)

max= a * max;
min=(1 < min * a) ? 1 : min * a ;

else if (a<0)

max=(1 > min * a) ? 1 : min * a ; min=max * a;

else

max=1; min=1;

ans=(ans > max) ? ans : max; // this is outside else

}

at the end of loop max will be the answer, happy coding :)

Upvotes: 0

xashru
xashru

Reputation: 3580

Your dp state depends on both the current index n and the current result p. So you need to memoize the result in a 2D array instead of using a 1D array for just index.

private int f(int[] a, int p, int n, int[] dp) {
    if(dp[n][p]!=0)
        return dp[n][p];
    if(n==a.length)
        dp[n][p] = p;
    else
        dp[n][p] = max(p, f_m(a, p*a[n], n+1, dp), f_m(a, a[n], n+1, dp));
    return dp[n][p];
}

Upvotes: 1

Related Questions