連続サブ配列の最大和(Maximum Subaray)

連続するサブ配列の最大和を求めて、ここは道の例題LeetCode|Maximum Subarayがあります
Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
方法一:O(n)の動的計画解法

class Solution {
public:
    int maxSubArray(vector& nums) {
        if(nums.size() == 0) return 0;
        int res = 0, sum = 0;
        bool allNegtive = true;
        for(int i = 0; i < nums.size(); i++){  // [-2, 1], disgard the first
            if( sum + nums[i] > 0){
                sum += nums[i];
                allNegtive = false;
            } else {
                sum = 0;
            }
            res = max(res, sum);
        }
        if(allNegtive){
            res = nums[0];
            for(int i = 1; i < nums.size(); i++){
                res = max(res, nums[i]);
            }
        }
        return res;
    }
};

方法2:上記のダイナミックプランニングを改良し、すべて負の場合を考慮する必要はありません.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int cur = nums[0], res = cur;
        for(int i = 1; i < nums.size(); ++i){
            cur = max(nums[i], cur+nums[i]);
            res = max(cur, res);
        } return res;
    }
};

方法3:n lognの分治法(cont.)

class Solution {
public:
    int maxsum(vector<int>& arr, int l, int r){
        if(l == r) return arr[l];
        int m = l + (r-l)/2;
        int cur = arr[m], lmax = arr[m], rmax = arr[m];
        for(int i = m-1; i >= l; --i){
            cur += arr[i];
            lmax = max(lmax, cur);
        }
        cur = arr[m];
        for(int i = m+1; i <= r; ++i){
            cur += arr[i];
            rmax = max(rmax, cur);
        }
        int ans = lmax+rmax-arr[m];
        if(l <= m-1) ans = max(ans, maxsum(arr, l, m-1));
        if(m+1 <= r) ans = max(ans, maxsum(arr, m+1, r));
        return ans;
    }

    int FindGreatestSumOfSubArray(vector<int> arr) {
        if(arr.size() == 0) return 0;
        return maxsum(arr, 0, arr.size()-1);
    }
};