53.maximum subarray

class  {
    public int maxSubArray(int[] nums) {
        return findMaxSubarray(nums, 0, nums.length-1);
    }
    public int findMaxCrossingSubArray(int[] nums, int low, int mid, int high){                                 
        int left_sum = Integer.MIN_VALUE;
        int sum1 = 0;
        int max_left=mid, max_right=mid; 
        for(int i=mid;i>=low;i--){
            sum1 = sum1+nums[i];
            if(sum1>left_sum){
                left_sum = sum1;
                max_left = i;
            }
        }
        int right_sum = Integer.MIN_VALUE;
        int sum2 = 0;
        for(int j=mid+1;j<=high;j++){
            sum2 = sum2+nums[j];
            if(sum2>right_sum){
                right_sum = sum2;
                max_right = j;
            }
        }
        return left_sum+right_sum;
    }
    
    public int findMaxSubarray(int[] nums, int low, int high){
        if(high==low)
            return nums[low];
        else{
            int mid = (high+low)/2;
            int left_sum = findMaxSubarray(nums, low, mid);
            int right_sum = findMaxSubarray(nums, mid+1, high);
            int cross_sum = findMaxCrossingSubArray(nums, low, mid, high);
            
            if(left_sum>=right_sum && left_sum>=cross_sum)
                return left_sum;
            if(right_sum>=left_sum && right_sum>=cross_sum)
                return right_sum;
            else return cross_sum;
        }
    }
}

class  {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE, sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum < 0) 
                sum = nums[i];
            else 
                sum += nums[i];
            if (sum > max)
                max = sum;
        }
        return max;
    }
}