LeetCode_ 53 (maximum subarray and)

Title Description ： Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .

A subarray is a continuous part of an array .

Example 1：
Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6 .

Example 2：
Input ：nums = [1]
Output ：1

Example 3：
Input ：nums = [5,4,-1,7,8]
Output ：23

Tips ：
1 <= nums.length <= 105
-104 <= nums[i] <= 104

Method 1 ： Divide and conquer method （ recursive ）

class Solution {
    
    /**
     *  Transition method 
     * @param nums  Original array 
     * @return   Returns the largest subsegment and 
     */
    public static int maxSubArray(int[] nums) {
    
        return MaxSubArray(nums,0,nums.length-1);
    }

    /**
     *  Find the largest subsegment and 
     * @param nums   Array to be found 
     * @param left   Left pointer 
     * @param right  Right pointer 
     * @return   Maximum sub sum 
     */
    public static int MaxSubArray(int[] nums,int left,int right) {
    
        int res=0,leftsum,rightsum,midsum,center;
        int sum1,sum2,leftsum1,rightsum1;
        if(left==right){
                    // Recursion end condition 
            res=nums[left];             // Recurse until there is only one element left in the sub segment , Then the maximum sum of sub segments is the element 
        }else{
    
            center=(left+right)/2;      // Take the middle element and divide the array into two segments , Divide and rule 
            leftsum=MaxSubArray(nums,left,center);// Recursively find the sum of the largest sub segments on the left 
            rightsum=MaxSubArray(nums,center+1,right);// Recursively find the sum of the largest sub segments on the right 
            sum1=-1230000000;leftsum1=0;// hypothesis sum1 For a very small number , Find the left maximum sub segment sum 
            for (int i = center; i >=left ; i--) {
    
                leftsum1+=nums[i];
                if(leftsum1>sum1)sum1=leftsum1;
            }
            sum2=-1230000000;rightsum1=0;// hypothesis sum2 For a very small number , Find the sum of the right largest subsegments 
            for (int i = center+1; i <=right ; i++) {
    
                rightsum1+=nums[i];
                if(rightsum1>sum2)sum2=rightsum1;
            }
            midsum=sum1+sum2;
            int s;
            if(leftsum>rightsum)s=leftsum;
            else s=rightsum;
            if(s>midsum)res=s;
            else res=midsum;
        }
        return res;
    }
}

Method 2 、 Dynamic programming