最大サブ配列問題(分治アルゴリズム)--アルゴリズム導論
1836 ワード
コード(『アルゴリズム導論』の偽コードを参照):
#include
const int ∞ = -1000000;
int max_left=0;
int max_right=0;
using namespace std;
int FindMaxCrossSubarray(int A[], int low, int mid, int high)
{
int left_sum = ∞;
int sum = 0;
for (int i = mid; i >= low; i--)
{
sum += A[i];
if (sum >left_sum)
{
left_sum = sum;
max_left = i;
}
}
int right_sum = ∞;
sum = 0;
for (int i = mid + 1; i <= high; i++)
{
sum += A[i];
if (sum > right_sum)
{
right_sum = sum;
max_right = i;
}
}
return (max_left,max_right,left_sum + right_sum);
}
int FindMaxSubarray(int A[], int low, int high)
{
int left_sum, right_sum, cross_sum,left_low,left_high,right_low,right_high,cross_low,cross_high;
if (high == low) //
{
return (low,high,A[low]);
}
else
{
int mid = (low + high) / 2; //
(left_low,left_high,left_sum) = FindMaxSubarray(A, low, mid); //
(right_low,right_high,right_sum) = FindMaxSubarray(A, mid + 1, high); //
(cross_low,cross_high,cross_sum) = FindMaxCrossSubarray(A, low, mid, high); //
if (left_sum >= right_sum && left_sum >= cross_sum)
return (left_low,left_high,left_sum);
else if (right_sum >= left_sum && right_sum >= cross_sum)
return (right_low,right_high,right_sum);
else //
return (cross_low,cross_high,cross_sum);
}
}
int main()
{
int a[] = {10, -43, 25, 20, 3, -6, -13, 18, -20, 7, 10, -7, -2, 15, -41, 17};
int length = sizeof(a) / sizeof(int);
cout<"<