这是最大子数组和算法的动态编程版本的工作方式吗?

Question

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

基本上，您有一个大小为 n 的数组A，并且您希望找到该数组的最大子数组总和。具有最大总和的子数组可以位于数组的右半部分、左半部分或中间的某个位置。因此，您递归调用该函数以计算数组左侧的最大子数组总和，然后从数组右侧计算。然后，计算从数组中间到末尾的最大子数组总和，然后计算从数组中间到开头的最大子数组总和（它的长度不一定是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);    
}  

Answer 1

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