CODEWITHSUNDEEP
javadynamic-programming
Craig
Craig

Reputation: 405

Building Maximum Subarray Dynamic Programming solution from Recursive Solution

I managed to solve the maximum subarray problem with dynamic programming before considering the recursive implementation, however, since I struggle with more complicated dynamic programming problems I decided to work on fundamentals like seeing the recursive solution I'm implementing and then converting it to a dynamic one.

The dynamic programming solution I have is as follows:

int[] dp = new int[arr.length];

if (arr.length == 0)
{
        return 0;
}

//initialize
dp[0] = Math.max(0, arr[0]);
int max = dp[0];

for (int i = 1; i < arr.length; i++)
{
    dp[i] = Math.max(0, arr[i] + dp[i - 1]);

    if (dp[i] > max)
    {
        max = dp[i];
    }
}

return max;

When I started thinking of recursive implementations I couldn't seem to find the correct one that leads to this logic though. The only recursive solution I've come up with is one that just splits the array into subsections:

public static int maxsubarrayR(int[] arr, int start, int end)
{
    if (start == end)
    {
        return 0;
    }
    else
    {
        return Math.max(sum(arr, start, end), Math.max(maxsubarrayR(arr, start + 1, end), maxsubarrayR(arr, start, end - 1)));
    }
}

which involves an additional elementary sum method. Could someone show the recursive implementation that leads to the dynamic programming solution?

Upvotes: 0

Views: 490

Answers (1)

Aristofanio Garcia
Aristofanio Garcia

Reputation: 1123

Your arr works like a global variable so we can only use it as parameter. Your dp is an auxiliar variable, a pivot for next iteration. Your max is a variable objective. All working is done in:

pivot = Math.max(0, arr[i] + pivot);
if (pivot >= max){
  max = pivot;
}

So you can try this:

private static int resolveR(int i, int max, int pivot, int[] arr){
  //initialize
  if (i == arr.length){
    return max;
  } else {
    pivot = Math.max(0, arr[i] + pivot);
    if (pivot >= max){
        max = pivot;
    }
    return resolveR(i+1, max, pivot, arr);
  }
}

See in action here: http://ideone.com/qvs1lJ

Upvotes: 2

Related Questions