.leetcode(53. Maximum Subarray)

문제

https://leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

문제 풀기 전

1. prev하고 max값을 잘 들고 있으면 O(n)으로 풀 수 있겠다.
2. min값이 integer min max이므로 max의 자료형을 long으로 해야겠다.

직접 푼 풀이

소요시간: 24분(16:09 ~ 16:33)

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null) {
            return 0;   
        }
        if (nums.length == 0) {
            return nums[0];   
        }

        long max = Long.MIN_VALUE;
        int prev = 0;
        for (int i=0; i<nums.length; i++) {
            int candidate = prev + nums[i];
            if (nums[i] >= candidate) {
                candidate = nums[i];
            }
            prev = candidate;

            if ( max <= candidate) {
                max = candidate;
                prev = candidate;
            }
        }

        return (int)max;
    }
}

느낀점

1. 솔루션의 3가지 방법중 Greedy방법이다. 솔루션은 나보다 더 간결하게 나타내었다. 어쨌뜬 원리는 비슷하다.
2. The problem is a classical example of divide and conquer approach이라고 나올정도로 복잡하고 사실 시간복잡도도 NlogN으로 더 걸리는데 한번 dq로 풀어보았다. 개념적으로 나눠서 접근하는게 신기했다. 결국 dq도 recursion을 쓰는거구나 라는 생각도 들었다.

솔루션 공부 후 추가로 푼 풀이

#dq로 풀이
class Solution {
    public int maxSubArray(int[] nums) {
        return dq(nums, 0, nums.length-1);
    }

    private int dq(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        int mid = (left+right)/2;

        int leftSum = dq(nums, left, mid);
        int rightSum = dq(nums, mid+1, right);
        int currSum = currSum(nums, left, right, mid);

        return Math.max(Math.max(leftSum, rightSum), currSum);
    }

    private int currSum(int[] nums, int left, int right, int mid) {
        if (left == right) {
            return nums[left];
        }

        int maxSum = Integer.MIN_VALUE;
        int leftSum = 0;
        for(int i=mid; i>left-1; i--) {
            leftSum += nums[i];
            maxSum = Math.max(leftSum, maxSum);
        }
        leftSum = maxSum;

        maxSum = Integer.MIN_VALUE;
        int rightSum = 0;
        for(int i=mid+1; i<right+1; i++) {
            rightSum += nums[i];
            maxSum = Math.max(rightSum, maxSum);
        }
        rightSum = maxSum;

        return leftSum + rightSum;
    }

}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)