题目描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

样例
输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

算法1

分治

思路：和归并排序一毛一样
居然ac了，还以为要用dp才能做…

时间复杂度

O(nlgn)

参考文献

算法导论 P43

C++ 代码

class Solution {
public:
    const int MIN = 0x80000001;
    //const int MAX = 0x7fffffff;
    int crossMax(vector<int> &nums,int lo, int mid, int hi){
        int l_max = MIN;
        int sum = 0;
        for(int i = mid; i >= lo ; i --){
            sum += nums[i];
            if(sum > l_max){
                l_max = sum;
            }
        }

        int r_max = MIN;
        sum = 0;
        for(int i = mid + 1; i <=hi ; i++){
            sum += nums[i];
            if(sum > r_max){
                r_max = sum;
            }
        }
        return l_max + r_max;
    }
    int maxS(vector<int> &nums,int lo ,int hi){
        if(lo == hi ) return nums[lo];
        else {
            int mid = (lo + hi) / 2;
            int maxl = maxS(nums,lo,mid);
            int maxr = maxS(nums,mid+1,hi);
            int maxMid = crossMax(nums,lo,mid,hi);
            int tmp = maxr > maxMid ? maxr : maxMid;
            return (maxl > (tmp ) ? maxl : tmp);
        }
    }
    int maxSubArray(vector<int>& nums) {
        return maxS(nums,0,nums.size()-1);
    }
};