最大子数组和_分治法求解

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组
是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

算法

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) { return sol(0, nums.size(), nums); }

    int sol(int left, int right, vector<int>& nums) {
        // 一个元素
        if (right - left == 1) {
            return nums[left];
        }
        // 多个元素
          // 拆
        int mid = left + (right - left) / 2;
        // 找中间位置，划分
        // 求解
        // 左数组 [left,mid)
        int sum_L = sol(left, mid, nums);
        // 右数组 mid,right
        int sum_R = sol(mid, right, nums);
        // 横跨左右数组
        int sum_M = 0;
        int crossing_l = -1;
        int crossing_r = -1;
        find_max_crossing_subarray(left, right, mid, nums, crossing_l,
                                   crossing_r, sum_M);
        // 合
        if (sum_L > sum_M && sum_L > sum_R) {
            return sum_L;
        } else if (sum_M > sum_R) {
            return sum_M;
        } else {
            return sum_R;
        }
    }
    // 数组左边界，右边界，中间值， 最大和的左边界，右边界，和
    int find_max_crossing_subarray(int left, int right, int mid,
                                   vector<int>& nums, int& l, int& r,
                                   int& res) {

        int max = INT_MIN;
        int sum = 0;
        // 左边最大left,mid+1
        for (int i = mid; i >= left; i--) {
            sum+=nums[i];
            if (sum > max) {
                max = sum;
                l = i;
            }
        }
        // 右边最大mid+1,right
        sum = max;
        for (int i = mid + 1; i < right; i++) {
            sum += nums[i];
            if (sum > max) {
                max = sum;
                r = r + 1;
            }
        }
        res = max;
        return max;
    }
};