LeetCode 문제 풀이 의 53. Maximum Subarray (연속 하위 배열 의 최대 와 문제)

53. Maximum Subarray (연속 서브 배열 의 최대 와 문제)
제목 설명 과 난이도

제목 설명:

정수 배열 nums 을 지정 하고 최대 와 연속 적 인 하위 배열 (하위 배열 은 최소 하나의 요 소 를 포함) 을 찾 아 최대 와 합 을 되 돌려 줍 니 다.
예시:

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

진급:
만약 당신 이 복잡 도가 O (n) 인 해법 을 실현 했다 면 더욱 정교 한 분 치 법 으로 구 해 를 시도 해 보 세 요.

난이도: 간단 합 니 다.

영어 사이트: 53. Maximum Subarray.

중국어 사이트 주소: 53. 최대 하위 순서 와.

사고 분석.
풀이 관건: 연속 서브 배열 의 문 제 는 일반적으로 우 리 는 현재 옮 겨 다 니 는 요소 로 끝 나 는 그 서브 배열 에 착안 하여 이렇게 분석 하면 문 제 를 간소화 할 수 있다.
참고 해답
참조 해답 1

public class Solution {

    //          nums ，               （           ），      。

    /**
     *     ：
     * dp[i] ：     nums[i]             
     * 

     *       ：
     * dp[i] = max{num[i],dp[i-1] + num[i]}
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        }
        //      ，          
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

참고 해답 2: 참고 해답 1 과 같 습 니 다. 옮 겨 다 니 는 과정 에서 가장 좋 은 해답 을 구 했 을 뿐 입 니 다.

public class Solution2 {

    /**
     *   Solution   ，       
     *      ：O(n)
     *      ：O(1)
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int segmentSum = nums[0];
        int res = nums[0];
        for (int i = 1; i < len; i++) {
            segmentSum = Math.max(nums[i], segmentSum + nums[i]);
            res = Math.max(res, segmentSum);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        Solution2 solution = new Solution2();
        int maxSubArray = solution.maxSubArray(nums);
        System.out.println(maxSubArray);
    }
}

참고 해답 3: 분 치 사상 을 사용 하면 개인 적 으로 좀 번거롭다 고 생각 하지만 우 리 는 이 문 제 를 통 해 분 치 사상 을 이해 할 수 있다.

public class Solution3 {

    /**
     *           
     * https://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        return maxSubArraySum(nums, 0, len - 1);
    }

    /**
     *       nums[mid]     
     *
     * @param nums
     * @param l
     * @param m
     * @param r
     * @return
     */
    private int maxCrossingSum(int[] nums, int l, int m, int r) {
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        //       nums[mid]   ，         
        //      ，       
        //     mid            
        for (int i = m; i >= l; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        //        nums[mid]   ，         
        //     mid+1            
        for (int i = m + 1; i <= r; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;

    }

    /**
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private int maxSubArraySum(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        int mid = l + (r - l) / 2;
        return max3(maxSubArraySum(nums, l, mid),
                maxSubArraySum(nums, mid + 1, r),
                maxCrossingSum(nums, l, mid, r));
    }

    private int max3(int num1, int num2, int num3) {
        return Math.max(num1, Math.max(num2, num3));
    }
}

이 글 의 주 소 는?https://liweiwei1419.github.io/leetcode-solution/leetcode-0053-maximum-subarray 만약 제 문제 풀이 에 잘못 이 있 거나 더 좋 은 해법 이 있다 면 저 에 게 알려 주 십시오[email protected] 。