LeetCode: 53번 (Maximum Subarray) [JAVA]

문제 링크

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

Maximum Subarray - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 두 개의 변수, minAcc, acc 선언
2. for문을 통해 시작+1부터 전체 배열을 돌며(i), 시작부터 i - 1 구간까지의 구간과 최소합을 가진 구간 비교를 통해 최소합을 가진 구간 최신화
3. 그 다음 현재 값을 더해 시작부터 현재까지의 누적값 계산
4. (현재까지의 누적값 - 최소합을 가진 구간)과 답 중 더 큰 답을 저장
5. 답 반환

 초기 문제를 보았을 때 문제에서 의미하는 바는, 흔히 구간 탐색을 할 때 시작과 끝을 배열 속 다른 위치에 두며 그 사이 구간의 합을 체크하다보니 O(n^2)의 복잡도를 요구한다. 문제에서 요구하는 바로는 이를 O(n)으로 줄여야 하다보니, 한 쪽은 어느정도 값이 고정된 상태로 탐색을 하며 배열을 한 번 반복해야 한다.
 우선 배열을 전체적으로 돌며 할 수 있는 것은, 앞선 값들을 누적시켜가며 저장하여 시작~현재까지의 구간의 합을 알 수 있다. 그렇다면 현재 시작~현재까지의 구간 합 중 시작~최소합을 가지는 구간 까지를 알아낼 수 있다면, 이를 빼면 현재에서 최대값을 아는 구간을 알 수 있다. 물론 이 또한 O(n)의 복잡도로 해결할 수 있다. 처음부터 최소합을 가진 구간을 따로 변수로 두고, 매번 누적값 계산을 위해 for문을 돌 때마다 현재 - 1 까지의 구간과 최소값을 가진 구간을 비교해 가장 작은 최소합을 가진 구간을 최신화시켜나가면 된다.
 이렇게 전체 배열을 돌 때마다 시작~현재까지의 구간의 합과 시작~최소합을 가진 구간을 계산해 이를 뺀 다음, 이를 계속 답과 비교하면 최대 구간의 합을 알아낼 수 있다.

 

class Solution {
    public int maxSubArray(int[] nums) {
        int answer = nums[0];
        int minAcc = 0;
        int[] leftToRightAcc = new int[nums.length];
        leftToRightAcc[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            leftToRightAcc[i] = nums[i] + leftToRightAcc[i - 1];//현재까지의 구간 누적합 계산
            minAcc = Math.min(minAcc, leftToRightAcc[i - 1]);//이전까지의 구간 누적값 중 최소 계산
            answer = Math.max(answer, leftToRightAcc[i] - minAcc);//(현재까지 누적합 - 최소 누적값 구간)의 최대
        }

        return answer;
    }
}

class Solution_2 {//해결방법 1의 최적화 버전
    public int maxSubArray(int[] nums) {
        int answer = nums[0], minAcc = 0, acc = nums[0];

        for (int i = 1; i < nums.length; i++) {
            minAcc = Math.min(minAcc, acc);
            acc += nums[i];
            answer = Math.max(answer, acc - minAcc);
        }

        return answer;
    }
}

결과