Question

算法导论，分治法求最大子数组，求一个c语言代码

Answer 1

这题的思想是书上的（《算法导论》），代码当然也是按照书上伪码写出的；
#include <stdio.h>

int Find_Max_Crossing_SubArray(int A[], int low, int mid, int high)
{
   int left_sum = -0xff;
   int sum = 0;
   for (int i = mid; i >= low; i --)
   {
      sum += A[i];
      if (sum >left_sum)
      {
         left_sum = sum;
      }
   }
   int right_sum = -0xff;
   sum = 0;
   for (int j = mid + 1; j <= high; j ++)
   {
      sum += A[j];
      if (sum > right_sum)
      {
         right_sum = sum;
      }
   }
   return left_sum + right_sum;
}

int Find_Maximum_SubArray(int A[], int low, int high)
{
   int left_sum, right_sum, cross_sum;
   if (high == low)
   {
      return A[low];
   }
   else
   {
      int mid = (low + high) / 2;
      left_sum = Find_Maximum_SubArray(A, low, mid);
      right_sum = Find_Maximum_SubArray(A, mid + 1, high);
      cross_sum = Find_Max_Crossing_SubArray(A, low, mid, high);
      if (left_sum >= right_sum && left_sum >= cross_sum)
      {
         return left_sum;
      }
      else if (right_sum >= left_sum && right_sum >= cross_sum)
      {
         return right_sum;
      }
      else
      {
         return cross_sum;
      }
   }
}
int main()
{
    int A[100];
    int n;
    printf("Please input the number of numbers:");
    scanf("%d",&n);
    for (int i = 0; i < n; i ++)
    {
       scanf("%d",&A[i]);
    }
    printf("最大子序列的和为：%d",Find_Maximum_SubArray(A, 0, n - 1));
    return 0;
}

Answer 2

#include <stdio.h>

int Find_Max_Crossing_SubArray(int A[], int low, int mid, int high)
{
int left_sum = -0xff;
int sum = 0;
for (int i = mid; i >= low; i --)
{
sum += A[i];
if (sum >left_sum)
{
left_sum = sum;
}
}
int right_sum = -0xff;
sum = 0;
for (int j = mid + 1; j <= high; j ++)
{
sum += A[j];
if (sum > right_sum)
{
right_sum = sum;
}
}
return left_sum + right_sum;
}

int Find_Maximum_SubArray(int A[], int low, int high)
{
int left_sum, right_sum, cross_sum;
if (high == low)
{
return A[low];
}
else
{
int mid = (low + high) / 2;
left_sum = Find_Maximum_SubArray(A, low, mid);
right_sum = Find_Maximum_SubArray(A, mid + 1, high);
cross_sum = Find_Max_Crossing_SubArray(A, low, mid, high);
if (left_sum >= right_sum && left_sum >= cross_sum)
{
return left_sum;
}
else if (right_sum >= left_sum && right_sum >= cross_sum)
{
return right_sum;
}
else
{
return cross_sum;
}
}
}
int main()
{
int A[100];
int n;
printf("Please input the number of numbers:");
scanf("%d",&n);
for (int i = 0; i < n; i ++)
{
scanf("%d",&A[i]);
}
printf("最大子序列的和为：%d",Find_Maximum_SubArray(A, 0, n - 1));
return 0;
}
听说回答的够长才能够自动采纳

追问

可惜没注释，不过还是谢了