java - 从递归解构建最大子数组动态规划解

Question

在考虑递归实现之前，我设法用动态编程解决了最大子数组问题，但是，由于我正在努力解决更复杂的动态编程问题，所以我决定研究基础知识，例如查看我正在实现的递归解决方案，然后将其转换到动态的。

我的动态规划解决方案如下:

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;

当我开始考虑递归实现时，我似乎找不到导致这一逻辑的正确实现。我想出的唯一递归解决方案是将数组分成几个小部分:

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)));
    }
}

其中涉及一个额外的基本求和方法。有人可以展示导致动态编程解决方案的递归实现吗？

Answer 1

你的arr就像一个全局变量，所以我们只能将它用作参数。 您的 dp 是一个辅助变量，是下一次迭代的枢轴。 您的最大值是一个可变目标。 所有工作均在以下位置完成:

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

所以你可以尝试这个:

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);
  }
}

在此处查看实际操作:http://ideone.com/qvs1lJ