algorithm - 每个递归算法都是分而治之的算法吗？

Question

我的作业有问题，我需要用分而治之的算法来解决这个问题。

我使用递归解决了这个算法。我是否通过使用递归自动使用分而治之？

例如，下面的方法是分而治之的算法吗？因为我在fun中使用了fun函数。(递归调用)

代码:

    #include <stdio.h>

/* int a[] = {-6,60,-10,20}; */
int a[] =  {-2, -3, 4, -1, -2, 1, 5, -3};
int len = sizeof(a)/sizeof(*a);
int maxherearray[10];

int fun(int n);
int max(int a, int b);
int find_max(int a[], int len);
void print_array(int a[], int start_idx, int end_idx);

int start_idx = 0;  // Start of contiguous subarray giving max sum
int end_idx = 0;    // End of contiguous subarray giving max sum

#define NEG_INF (-100000)

int max_sum = NEG_INF;  // The max cont sum seen so far.

int main(void)
{
    start_idx = 0;
    end_idx = len - 1;
    maxherearray[0] = a[0];

    printf("Array a[]: ");
    print_array(a, 0, len-1);
    printf("\n");

    // Compute the necessary information to get max contiguous subarray
    fun(len - 1);
    printf("Max subarray value == %d\n", find_max(maxherearray, len));
    printf("\n");

    printf("Contiguous sums: ");
    print_array(maxherearray, 0, len - 1);
    printf("\n");

    printf("Contiguous subarray giving max sum: ");
    print_array(a, start_idx, end_idx);
    printf("\n\n");

    return 0;
}

int fun(int n)
{
    if(n==0)
        return a[0];

    int max_till_j = fun(n - 1);

    // Start of new contiguous sum
    if (a[n] > a[n] + max_till_j)
    {
        maxherearray[n] = a[n];

        if (maxherearray[n] > max_sum)
        {
            start_idx = end_idx = n;
            max_sum = maxherearray[n];
        }
    }
    // Add to current contiguous sum
    else
    {
        maxherearray[n] = a[n] + max_till_j;

        if (maxherearray[n] > max_sum)
        {
            end_idx = n;
            max_sum = maxherearray[n];
        }
    }

    return maxherearray[n];
}

int max(int a, int b)
{
    return (a > b)? a : b;
}

// Print subarray a[i] to a[j], inclusive of end points.
void print_array(int a[], int i, int j)
{
    for (; i <= j; ++i) {
        printf("%d ", a[i]);
    }
}

int find_max(int a[], int len)
{
    int i;
    int max_val = NEG_INF;
    for (i = 0; i < len; ++i)
    {
        if (a[i] > max_val)
        {
            max_val = a[i];
        }
    }

    return max_val;
}

Answer 1

每个递归函数都不一定是分而治之的方法。还有其他方法，如减少和征服(减少一个常数因子、减少一个、可变大小减少)。

Is this below approach a divide an conquer algorithm?

您的函数恰好减少了一个常数因子，即 1 方法。可以扫一眼here .

分而治之算法的伪代码寻找最大子数组

MaxSubarray(A,low,high)
//
if high == low   
   return (low, high, A[low]) // base case: only one element
else
   // divide and conquer
   mid = floor( (low + high)/2 )
   (leftlow,lefthigh,leftsum) = MaxSubarray(A,low,mid)
   (rightlow,righthigh,rightsum) = MaxSubarray(A,mid+1,high)
   (xlow,xhigh,xsum) = MaxXingSubarray(A,low,mid,high)
   // combine
   if leftsum >= rightsum and leftsum >= xsum
      return (leftlow,lefthigh,leftsum)
   else if rightsum >= leftsum and rightsum >= xsum
      return (rightlow,righthigh,rightsum)
   else
      return (xlow,xhigh,xsum)
   end if
end if

--------------------------------------------------------------

MaxXingSubarray(A,low,mid,high)
// Find a max-subarray of A[i..mid]
leftsum = -infty
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > leftsum
       leftsum = sum
       maxleft = i
    end if
end for
// Find a max-subarray of A[mid+1..j]
rightsum = -infty
sum = 0
for j = mid+1 to high
    sum = sum + A[j]
    if sum > rightsum
       rightsum = sum
       maxright = j
    end if
end for
// Return the indices i and j and the sum of the two subarrays
return (maxleft,maxright,leftsum + rightsum)

-----------------------------------------------------------

=== Remarks:

(1) Initial call: MaxSubarray(A,1,n)

(2) Divide by computing mid.
    Conquer by the two recursive alls to MaxSubarray.
    Combine by calling MaxXingSubarray and then determining
       which of the three results gives the maximum sum.

(3) Base case is when the subarray has only 1 element.