分治アルゴリズムは最長男のシーケンスとを求めます

1216 ワード

配列を2つの部分に分けると、最長子配列が中線の左側の配列、右の配列、または一部が左、一部が右に現れる可能性があります.左,右配列の最長子シーケンスは,前法に従って解くことができ,再帰的にプログラムを実現することができる.
#include 
#include 
using namespace std;
int max3(int a, int b, int c)
{
	return max(max(a, b), c);
}
int MaxSubSum(int *a, int left, int right)
{
	int maxLeftSum = 0, maxRightSum = 0;
	int leftBorderSum = 0, rightBorderSum=0;
	int maxLeftBorderSum = 0, maxRightBorderSum = 0;
	if (left == right)
		return a[left] > 0 ? a[left] : 0;
	int mid = (left + right) / 2;
	maxLeftSum = MaxSubSum(a, left, mid);
	maxRightSum = MaxSubSum(a, mid + 1, right);
	for (int i = mid; i >= left; --i)
	{
		leftBorderSum += a[i];
		if (leftBorderSum > maxLeftBorderSum)
			maxLeftBorderSum = leftBorderSum;
	}
	for (int i = mid + 1; i <= right; ++i)
	{
		rightBorderSum += a[i];
		if (rightBorderSum > maxRightBorderSum)
			maxRightBorderSum = rightBorderSum;
	}
	int maxBorderSum = maxRightBorderSum + maxLeftBorderSum;
	return max3(maxLeftSum, maxRightSum, maxBorderSum);
}
int MaxSubSequenceSum(int *a, int n)
{
	return MaxSubSum(a,0,n - 1);
}

int main()
{
	int a[]{ 4, -3, 5, -2, -1, 2, 6, -2 };
	cout << MaxSubSequenceSum(a, 8);
}