LeetCode53 | 最大子序和

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

---

     求最大子数组的方法，可以参考这一篇文章，讲了三种方法：递归与分治 / 序列DP | 最大子数组问题。

     我采用的是简单的分治算法，ac代码如下：

#include <algorithm>
using namespace std;

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

    int findMaxSubarray(vector<int>& a, int s, int e) {
        if(s == e)  //递归的终点
            return a[s];

        int mid = (s + e) / 2;

        int leftAns = findMaxSubarray(a, s, mid);  //计算含mid的左侧答案
        int rightAns = findMaxSubarray(a, mid + 1, e);  //计算不含mid的右侧答案
        int midAns = findMAxCrossingSubarray(a, s, mid, e);  //计算含mid的答案
        
        return max(midAns, max(leftAns, rightAns));
    }

    /* 在数组a[l,r]内找到包含m下标位置的最大子数组 */
    int findMAxCrossingSubarray(vector<int>& a, int l, int mid, int r) {
        //左边
        int leftMax = a[mid], cur = a[mid];
        for(int i = mid - 1; i >= l; i--) {
            cur += a[i];
            leftMax = max(cur, leftMax);   //更新最大答案
        }
        //右边
        int rightMax = a[mid];
        cur = a[mid];
        for(int i = mid + 1; i <= r; i++) {
            cur += a[i];
            rightMax = max(cur, rightMax);
        }

        return leftMax + rightMax - a[mid];
    }
    
};