相连最大子序列和的分治算法O(nlog(n))

maxSubSum3.cpp

/**
 * @param a
 * @param left
 * @param right
 * @return maxSum between left and right
 * @brief 相连最大子序列和的递归算法
 * @note 找出生成 [left ... right] 的子数组的最大和，不试图保留具体的最佳序列
 */
int maxSumRec(const vector<int> &a, int left, int right) {
    if (left == right) // 基准情形
        if (a[left] > 0)
            return a[left];
        else
            return 0;

    int center = (left + right) / 2;
    int maxLeftSum = maxSumRec(a, left, center);
    int maxRightSum = maxSumRec(a, center + 1, right);

    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for (int i = center; i >= left; --i) {
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }

    int maxRightBorderSum = 0, rightBorderSum = 0;
    for (int i = center + 1; i <= right; ++i) {
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }

    return max(maxLeftBorderSum + maxRightBorderSum,
               max(maxLeftSum, maxRightSum));
}

/**
 * @param a
 * @return maxSum between [0 ... a.size()]
 * @brief 相连最大子序列和的分治算法
 * @note 驱动程序
 */
int maxSubSum3(const vector<int> &a) {
    return maxSumRec(a, 0, a.size() - 1);
}