分治法实现Maximum Subarray算法如何返回最大子数组起止索引

• 首先定义自定义结构体，同时存储最大子数组的和、起始索引、结束索引，替换原有函数的int类型返回值
• 调整maxCrossingSum函数：计算跨中点最大和的过程中同步记录左边界、右边界，和总和一起返回
• 调整maxSubarraySum递归函数：每次递归得到左半区、右半区、跨中三个子问题的结果后，比较三者的和，返回和最大的那组结果

#include <limits.h>
#include <stdio.h>

// 定义返回结果结构体：存储最大子数组的和、起始索引、结束索引
typedef struct {
    int sum;
    int left;
    int right;
} SubarrayResult;

// 计算跨中点的最大子数组结果
SubarrayResult maxCrossingSum(int A[], int l, int mid, int r) {
    SubarrayResult res;
    int sum = 0;
    int lsum = INT_MIN;
    int left_idx = mid;
    // 遍历左半部分，找最大和对应的左边界
    for (int i = mid; i >= l; i--) {
        sum += A[i];
        if (sum > lsum) {
            lsum = sum;
            left_idx = i;
        }
    }

    sum = 0;
    int rsum = INT_MIN;
    int right_idx = mid + 1;
    // 遍历右半部分，找最大和对应的右边界
    for (int i = mid + 1; i <= r; i++) {
        sum += A[i];
        if (sum > rsum) {
            rsum = sum;
            right_idx = i;
        }
    }

    res.sum = lsum + rsum;
    res.left = left_idx;
    res.right = right_idx;
    return res;
}

// 递归求解最大子数组
SubarrayResult maxSubarraySum(int A[], int low, int high) {
    SubarrayResult res;
    // 递归终止条件：只有一个元素
    if (low == high) {
        res.sum = A[low];
        res.left = low;
        res.right = high;
        return res;
    }

    int mid = low + (high - low) / 2;
    SubarrayResult left_res = maxSubarraySum(A, low, mid);
    SubarrayResult right_res = maxSubarraySum(A, mid + 1, high);
    SubarrayResult cross_res = maxCrossingSum(A, low, mid, high);

    // 比较三个结果，返回和最大的
    if (left_res.sum >= right_res.sum && left_res.sum >= cross_res.sum) {
        return left_res;
    } else if (right_res.sum >= left_res.sum && right_res.sum >= cross_res.sum) {
        return right_res;
    } else {
        return cross_res;
    }
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    SubarrayResult result = maxSubarraySum(arr, 0, n-1);
    // 输出结果：最大子数组和为6，起始索引3，结束索引6（对应子数组[4,-1,2,1]）
    printf("最大子数组和：%d，起始索引：%d，结束索引：%d", result.sum, result.left, result.right);
    return 0;
}

内容的提问来源于stack exchange，提问作者user16438868