[Grind75-LeetCode] Maximum Subarray JAVA

반응형

728x90

[Grind75-LeetCode] Maximum Subarray - Medium 

---

접근

• 카데인 알고리즘 (Kadane's Algorithm)

---

풀이

Grind75의 2주 차 마지막 문제로 LeetCode에서 풀어보는 첫 Medium 난이도 문제이다. 이 문제는 주어진 트리 내 서브트리의 합 중 최댓값을 구하는 문제이다. 주어지는 트리가 int 배열의 형태이기 때문에 사실상 배열 내 연속되는 부분의 최댓값을 구하는 것과 동일하다. 보통 연속되는 부분의 최댓값을 구할 때 브루트 포스를 사용해 구해주면 간단하긴 하지만 아래의 추가 내용으로 "만약 이 문제를 O(n) 성능으로 해결하는 법을 찾았다면 분할 정복 방법으로 도전해 봐라"라는 문구가 있기에 이 문제는 O(n) 성능으로 해결이 가능하다는 말인 거 같다. 그렇다면 자연스럽게 브루트 포스는 사용이 불가하고 다른 접근 법을 통해 문제를 해결해야 한다.

 

이 문제는 카데인 알고리즘을 사용해 풀 수 있는 문제이다. 카데인 알고리즘은 주어진 정수 배열에서 가장 큰 합을 가지는 연속 부분 배열의 합을 찾기 위해 설계된 효율적인 알고리즘으로 1980년대에 일본의 수학자 요시노리 카데인(Yoshinori Kadane)에 의해 개발 되었다고 한다. 카데인 알고리즘은 현재 연속 부분 배열의 합을 지속적으로 추적하고 더 이상 연속 부분 배열의 최대 합이 증가하지 않는 경우에 새로운 부분 배열을 시작하는 것이다. 그렇게 불필요한 계산을 피하여 O(n) 성능으로 해결이 가능하다. 

    public int maxSubArray(int[] nums) {
        int maxSum = nums[0]; 
        int currentMax = nums[0]; 

        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSum = Math.max(maxSum, currentMax);
        }

        return maxSum;
    }

연속된 최댓값을 저장하는 maxSum 변수와 현재 더 큰 값을 저장하는 currentMax 변수를 가지고 풀어나가게 된다. 각각 변수는 배열의 첫 번째 값으로 초기화되고 배열을 순회하며 값이 업데이트된다. 최댓값을 저장하는 변수는 당연히 최대 값을 업데이트하게 되고 현재 현재 큰 값을 저장하는 변수는 현재 인덱스와 이전 인덱스까지의 합과 비교해 이전 인덱스 값의 합에 현재 인덱스 값을 더했을 때 더 큰 값을 만들 수 있을 경우 더하게 되고 그렇지 않을 경우 현재 인덱스 값을 새로운 부분합 시작으로 변경하게 된다. 

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

시작 maxSum = -2, currentMax = -2

nums[i] = 1
currentMax = Math.max(nums[i] = 1, currentMax + nums[i] = -2 + 1) = Math.max(1, -1)
currentMax + nums[i] < nums[i] -> nums[i] = 1에서 새로운 부분 배열을 시작하는게 더 효율적
currentMax = 1, maxSum = 1

nums[i] = -3
currentMax = Math.max(-3, 1 - 3) = Math.max(-3, -2)
currentMax + nums[i] > nums[i] -> 현재 인덱스와 currentMax를 더한것이 더 큰 값이기 때문에 부분 배열을 유지
currentMax = -2, maxSum = 1

nums[i] = 4
currentMax = Math.max(4, -2 + 4) = Math.max(4, 2)
currentMax + nums[i] < nums[i] -> nums[i] = 4에서 새로운 부분 배열 시작
currentMax = 4, maxSum = 4
.
.
.

---

전체 코드

class Solution {
    public int maxSubArray(int[] nums) {
        int currentMaxSum = nums[0]; 
        int currentMax = nums[0]; 

        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            currentMaxSum = Math.max(currentMaxSum, currentMax);
        }

        return currentMaxSum;
    }
}