0

在dynamic programming我的算法教科书的章节中，我有一个如何使用这种技术解决最大子数组和问题的示例。我不确定我是否理解了算法背后的想法，所以我将在这里描述我认为它是如何工作的（在阅读了几次关于它并做了几个例子之后）。

基本上，您有一个Asize数组n，并且您想找到该数组的最大子数组总和。总和最大的子数组可以位于数组的右半部分、左半部分或中间的某个位置。因此，您递归调用该函数以从左侧计算最大子数组总和，然后从数组右侧计算。然后，计算从数组中间到末尾的最大子数组和，然后计算从数组中间到开头的最大子数组和（它的长度不一定n/2）。然后，如果左边的最大子数组和加上右边的最大子数组和的和大于左半边的最大子数组和（递归计算的那个）和右半边的最大子数组和（也递归计算），则最大子数组和在中间。否则是左半部分和右半部分的最大值（这些是递归计算的）。

我得到算法的工作机制了吗？

这是我正在分析的功能：

int maxSubArraySum(int* arr, int n)
{
    if(n == 1)
    {
        return arr[0];
    }
    int m = n / 2;
    int left = maxSubArraySum(arr, m);
    int right = maxSubArraySum(arr + m, n - m);
    int leftsum = INT_MIN, rightsum = INT_MIN, sum = 0;

    for(int i = m; i < n; i++)
    {
        sum += arr[i];
        rightsum = std::max(rightsum, sum);
    }

    sum = 0;

    for(int i = (m - 1); i >= 0; i--)
    {
        sum += arr[i];
        leftsum = std::max(leftsum, sum);
    }

    int retval = std::max(left, right);
    return std::max(retval, leftsum + rightsum);    
}
4

1 回答 1

0

不需要总是递归来实现动态规划。Kadane 算法是动态规划的一个简单示例，通过将问题分解为重复使用 n-1 次的子问题（将迄今为止的最后一个最大子数组与当前的最大子数组进行 n-1 次比较）。

于 2015-06-20T11:17:35.463 回答