分治アルゴリズムは最長男のシーケンスとを求めます
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);
}