题目

给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

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

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contiguous-sequence-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：

class Solution {
   public int maxSubArray(int[] nums) {
            return num(nums,0, nums.length-1);
        }
        public int num(int[] nums, int start, int end){
            if(start==end){
                return nums[start];
            }
            int mid= (start+end)/2;
            int leftmax=num(nums,start,mid);
            int rightmax=num(nums,mid+1,end);
            return max(nums, leftmax,rightmax,start,mid,end);
        }
        public int max(int[] nums, int leftmax, int rightmax,int start, int mid, int end){
            int curleftmax=Integer.MIN_VALUE;
            int currightmax=Integer.MIN_VALUE;
            int sum=0;
            for(int i = mid;i>=start;i--){
               sum += nums[i];
                if(sum>curleftmax){
                    curleftmax=sum;
                }

            }
            sum=0;
            for(int i = mid+1; i<=end; i ++){
               sum += nums[i];
                if(sum>currightmax){
                    currightmax=sum;
                }
            }
            return Math.max(Math.max(leftmax,rightmax),(curleftmax+currightmax));
        }
}