用分治法解决最大子段和问题并求出最大子段和及下标范围C++

分治法通常用于复杂问题的递归分解，对于最大子段和问题（也称为Kadane's algorithm），它通过将序列分割成两个部分来查找每个部分的最大子段和，然后合并这两个结果来找到整个数组的最大子段和。以下是使用C++实现的基本思路：

#include <vector>
#include <climits>

// 辅助函数，返回给定区间内的最大子段和
int maxCrossingSum(const std::vector<int>& nums, int low, int mid, int high) {
    int leftMax = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= low; --i) {
        sum += nums[i];
        if (sum > leftMax)
            leftMax = sum;
    }
    
    int rightMax = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= high; ++i) {
        sum += nums[i];
        if (sum > rightMax)
            rightMax = sum;
    }

    return leftMax + rightMax;
}

// 主函数，计算整个数组的最大子段和
std::pair<int, std::pair<int, int>> kadanesAlgorithm(const std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0)
        return {0, {0, 0}};

    int maxSoFar = nums[0], currentMax = nums[0];

    int start = 0, end = 0;
    for (int i = 1; i < n; ++i) {
        // 如果当前元素加上前缀和大于当前最大值，更新最大值和起始位置
        if (nums[i] + currentMax > maxSoFar) {
            maxSoFar = nums[i] + currentMax;
            start = i - currentMax;
            end = i;
        }
        
        // 如果当前元素本身大于最大子段和，更新最大子段和
        if (nums[i] > currentMax) {
            currentMax = nums[i];
            start = i;
            end = i;
        }
    }

    return {maxSoFar, {start, end}};
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    auto result = kadanesAlgorithm(nums);
    std::cout << "最大子段和: " << result.first << "\n";
    std::cout << "子段下标范围: [" << result.second.first << ", " << result.second.second << "]" << std::endl;

    return 0;
}

在这个程序中，`kadanesAlgorithm`函数是核心，它首先检查整个数组是否为空，然后遍历数组，维护两个变量`maxSoFar`和`currentMax`分别记录到目前为止的最大子段和以及从当前位置开始的最大子段和。`start`和`end`变量用来保存最大子段和的起始和结束索引。