首页 > 代码库 > 最大子数组分治方案C++实现

最大子数组分治方案C++实现

以下实现最大子数组的分治策略,算法来自《算法导论》

#include<iostream>
using namespace std;
 
struct ans
{
    int low;
    int high;
    int sum;
};
 
ans MAXIMUM_CROSSING_SBUARRAY(int * A, int low, int mid, int high)
{
    ans cross_ans = {mid, mid, INT_MIN};
    ans cross_left = {mid, mid, INT_MIN};
    ans cross_right = {mid + 1, mid + 1, INT_MIN};
    int sum = 0;
    for(int i = mid; i >= low; --i)
    {
        sum += A[i];
        if(cross_left.sum < sum)
        {
            cross_left.sum = sum;
            cross_left.low = i;
        }
    }
    sum = 0;
    for (int j = mid + 1; j <= high; ++j)
    {
        sum += A[j];
        if(cross_right.sum < sum)
        {
            cross_right.sum = sum;
            cross_right.high = j;
        }
    }
    cross_ans.low = cross_left.low;
    cross_ans.high = cross_right.high;
    cross_ans.sum = cross_left.sum + cross_right.sum;
    return cross_ans;
}
 
ans MAXIMUM_SUBARRAY(int * A, int low, int high)
{
    if(low == high)
    {
        ans myans = {low, high, A[low]};
        return myans;
    }
    else
    {
        int mid = (low + high) / 2;
        ans leftans = MAXIMUM_SUBARRAY(A, low, mid);
        ans rightans = MAXIMUM_SUBARRAY(A, mid + 1, high);
        ans crossans = MAXIMUM_CROSSING_SBUARRAY(A, low, mid, high);
        if(leftans.sum > rightans.sum && leftans.sum > crossans.sum)
            return leftans;
        else if(rightans.sum > leftans.sum && rightans.sum > crossans.sum)
            return rightans;
        else
            return crossans;
    }
}
 
int main()
{
    int b[] = {3, -2, 5, -7, 3, 1, 1,-4, 9, -3};
    ans mybestans = MAXIMUM_SUBARRAY(b, 0, 9);
    cout << "The sub_array‘s elements of b with the greatest sum is the element from "<< mybestans.low << " to " << mybestans.high << endl;
    cout << "The sum is " << mybestans.sum << endl;
    return 0;
}

最大子数组分治方案C++实现