53.Maximum Subarray

Solution 1: Kadane's Algorithm O(N)

class Solution {
    public int maxSubArray(int[] nums) {
        int maxNow = nums[0];
        int maxSoFar = nums[0];
        for(int i = 1; i < nums.length; i++){
            maxNow = Math.max(maxNow + nums[i], nums[i]);
            maxSoFar = Math.max(maxSoFar, maxNow);
        }
        return maxSoFar;
    }
}

Solution 2: Divide and Conquer

class Solution {
public:
    int max_3(int a, int b, int c){
        a = max(a, b);
        a = max(a, c);
        return a;
    }
    int max_sub_sum(vector<int>&nums, int left, int right){
        int max_left_sum, max_right_sum;
        int max_left_border_sum, max_right_border_sum;
        int left_border_sum, right_border_sum;
        int middle, i;

        if(left==right){
            if(nums[left]>0)
                return nums[left];
            else{
                return 0;
            }
        }
        middle = left + (right-left)/2;
        max_left_sum = max_sub_sum(nums, left, middle);
        max_right_sum = max_sub_sum(nums, middle+1, right);

        max_left_border_sum = 0;
        left_border_sum = 0;
        for(i=middle; i>=left; i--){
            left_border_sum += nums[i];
            max_left_border_sum = max(left_border_sum, max_left_border_sum);
        }

        max_right_border_sum = 0;
        right_border_sum = 0;
        for(i=middle+1; i<=right; i++){
            right_border_sum += nums[i];
            max_right_border_sum = max(right_border_sum, max_right_border_sum);
        }

        return max_3(max_left_sum, max_right_sum, max_left_border_sum+max_right_border_sum);
    }
    int maxSubArray(vector<int>& nums) {
        //Pre_Condition: at least one element, or nums.size()-1 will error.
        int res=max_sub_sum(nums, 0, nums.size()-1);
        if(res==0){
            int tmp=nums[0];
            for(int i=1; i<nums.size(); i++){
                tmp=max(tmp, nums[i]);   
            }
            res = tmp;
        }
        return res;
    }
};