스냅 53 최대 자동 정렬 및

정수 그룹 nums 을 정하고, 최대 화합을 가진 연속 서브 그룹 (서브 그룹은 최소한 원소를 포함) 을 찾아 최대 화합을 되돌려줍니다.
예:

  : [-2,1,-3,4,-1,2,1,-5,4],
  : 6
  :       [4,-1,2,1]     ，  6。

동적 기획 방정식: dp[i]=max(dp[i-1]+nums[i],nums[i])
사고방식 1: O(n)

class Solution {
    public int maxSubArray(int[] nums) {
        int sum=0;
        int res=nums[0];
        for(int i=0;i0)
                sum+=nums[i];
            else
                sum=nums[i];
             res=Math.max(res,sum);
        } 
        return res;
    }
}

사고방식2: 분치법
왼쪽 부분에서 뒤에서 앞으로 찾기 (mid---0)
오른쪽 부분에서 이동해서 찾기 (mid+1--length),

class Solution {
    public int maxSubArray(int[] nums) {
        return maxSubArrayPart(nums,0,nums.length-1);
    }
    
    private int maxSubArrayPart(int[] nums,int left,int right){
        if(left==right){
            return nums[left];
        }
        int mid=(left+right)/2;
        return Math.max(
            maxSubArrayPart(nums,left,mid),
            Math.max(
                maxSubArrayPart(nums,mid+1,right),
                maxSubArrayAll(nums,left,mid,right)
            )
        );
    }

    
    private int maxSubArrayAll(int[] nums,int left,int mid,int right){
        int leftSum=0;
        int sum=0;
        for(int i=mid;i>=left;i--){
            sum+=nums[i];
            if(sum>leftSum){
                leftSum=sum;
            }
        }
        sum=0;
        int rightSum=Integer.MIN_VALUE;
        for(int i=mid+1;i<=right;i++){
            sum+=nums[i];
            if(sum>rightSum){
                rightSum=sum;
            }
        }
        return leftSum+rightSum;
    }
}