53. Maximum Subarray

 - 문제

다음 배열이 있다고 가정해보자.

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

 

이 때, 배열 내부의 연속된 서브 배열 중 합이 가장 큰 경우를 리턴

예를 들어, [4, -1, 2, 1]의 합은 6으로 서브 배열 중 합이 가장 크다.

 

 

 - 풀이

우선 for문을 1자리 중에서 최대값을 찾고, 2자리 중에서 내부 for문을 돌면서 찾으면 성능이 나오지 않는다.

여기서 카데인 알고리즘을 적용하면 배열을 한 번만 순회하여 O(n)의 시간복잡도로 해결할 수 있다.

 

일반적으로 배열을 순회하면서

1. 1자리의 합을 모두 구해서 최대값을 구함

2. 2자리의 합을 모두 구해서 최대값을 구함

...

n. n자리의 합을 모두 구해서 최대값을 구함

등과 같이 생각했다면, 이 문제는 정답은 나올지언정 성능은 나오지 않는다.

 

생각을 달리해서, 인덱스(i)를 1씩 순회시키면서 해당 배열까지 존재하는

1자리의 합, 2자리의 합, ... , n자리의 합을 한번에 구해야 한다.

 

수평적인 계산(?)이 아닌, 수직적인 계산(?) 을 통해 값을 구해야 한다는 것이다.

 

즉, '모든 n자리의 합' 을 먼저 구하는 것이 아니라, '해당 인덱스 자리까지의 n자리 합에 대한 값들'을 먼저 구하는 것이 키포인트다.

 

중요한 것은, 여기서 계산된 여러 값 중 최대값만 고려해서 계산해도 된다는 것이다.

 

그 이유는, '앞에서 이미 계산한 값은 변하지 않고, 이후에 +1을 더하든 +2를 더하든 현재 최대값에 연산한 값이 곧 또 다시 최대값이기 때문'이다.

단, 음수를 더하는 경우는 해당하지 않는다. 왜냐면, 이미 최대값에 음수를 더하면 최대값이 아니기 때문이다.

 

그림을 통해 살펴보자.

위 배열의 모든 서브 배열의 합을 구한 그림은 다음과 같다.

현재 최대값을 의미하는 currentMax는 i=n일 때 계산된 숫자 중 최대값을 의미하며,

결과를 리턴할 최종 최대값을 의미하는 max는 현재까지 나온 숫자 중 최대값을 의미한다.

 

 

 - i=0일 때

arr[i] = arr[0] = -2이며,

currentMax는 비어있으므로 -2로 갱신한다.

 

max는 현재 비어있으므로, max를 currentMax값인 -2로 갱신한다.

 

 

 - i=1일 때

arr[i] = arr[1] = 1이며,

currentMax는 currentMax + arr[1] = -2 + 1 = -1이 된다.

 

currentMax(-1)가 arr[1] (1)보다 작으므로, currentMax는 1로 갱신한다.

max(-2)가 currentMax(1)보다 작기 때문에, max는 1로 갱신한다

 

여기서 currentMax를 구할 때, 1자리의 합을 의미하는 arr[i]와 currentMax+arr[i] 2개만 비교하면 된다.

 

currentMax + arr[i]를 비교하는 이유는 현재까지 계산된 값 중 최대값이기 때문이다.

다시 말하지만, 이미 currentMax값이 정해진 상황에서 다른 수의 계산은 무의미하다.

다른 수에서 더한 만큼 currentMax에도 값이 더해질 것이기 때문에, 연산 후에도 여전히 currentMax+arr[i]의 값이 최대값이기 때문이다.

 

다만 1자리의 합을 의미하는 arr[i]는 뭐가 나올지 알 수 없는 상황이기 때문에 반드시 비교를 해야 한다.

currentMax가 음수일 수도 있기 때문이다.

예를 들어 currentMax가 -1이고, arr[i]가 1이라면

arr[i] = 1

currentMax + arr[i] = (-1) + 1 = 0

처럼 되기 때문에 max값이 달라질 수 있다.

 

 

 - i=2일 때

arr[i] = arr[2] = -3이며,

currentMax는 currentMax + arr[2] = 1 + (-3) = -2가 된다.

 

currentMax(-2)가 arr[2] (-3)보다 크므로 currentMax는 갱신하지 않는다.

또한 max(1)가 currentMax(-2)보다 크기 때문에, 갱신하지 않는다.

 

 

 - i=3일 때

arr[i] = arr[3] = 4이며,

currentMax는 currentMax + arr[3] = -2 + 4 = 2가 된다.

 

currentMax(2)가 arr[3] (4)보다 작으므로, currentMax는 4로 갱신한다.

max(1)가 currentMax(4)보다 작기 때문에, max는 4로 갱신한다.

 

 

 - i=4일 때

arr[i] = arr[4] = -1이며,

currentMax는 currentMax + arr[4] = 4 + (-1) = 3이 된다.

 

currentMax(3)가 arr[4] (-1)보다 크기 때문에, currentMax는 갱신하지 않는다.

max(4)가 currentMax(3)보다 크기 때문에, 갱신하지 않는다.

 

 

 - i=5일 때

arr[i] = arr[5] = 2이며,

currentMax는 currentMax + arr[5] = 3 + 2 = 5가 된다.

 

currentMax(5)가 arr[5] (2)보다 크기 때문에, currentMax는 갱신하지 않는다.

max(4)가 currentMax(5)보다 작기 때문에, max는 5로 갱신한다.

 

 

 - i=6일 때

arr[i] = arr[6] = 1이며,

currentMax는 currentMax + arr[6] = 5 + 1 = 6이 된다.

 

currentMax(6)가 arr[6] (1)보다 크기 때문에, currentMax는 갱신하지 않는다.

max(5)가 currentMax(6)보다 작기 때문에, max는 6으로 갱신한다.

 

 

 - i=7일 때

arr[i] = arr[7] = -5이며,

currentMax는 currentMax + arr[7] = 6 + (-5) = 1이 된다.

 

currentMax(1)가 arr[7] (-5)보다 크기 때문에, currentMax는 갱신하지 않는다.

max(6)가 currentMax(1)보다 크기 때문에, max는 갱신하지 않는다.

 

 

 - i=8일 때

arr[i] = arr[8] = 4이며,

currentMax는 currentMax + arr[8] = 1 + 4 = 5가 된다.

 

currentMax(5)가 arr[8] (4)보다 크기 때문에, currentMax는 갱신하지 않는다.

max(6)가 currentMax(5)보다 크기 때문에, max는 갱신하지 않는다.

 

 

for문이 다 돌았으므로 max값인 6을 리턴한다.

 

위 설명을 토대로 한 자바 소스코드는 다음과 같다.

public class MaximumSubarray {
    public int solution(int[] nums) {
        int currentMax = nums[0];
        int max = nums[0];
        int numsLength = nums.length;
        for (int i = 1; i < numsLength; i++) {

            if (nums[i] > currentMax + nums[i])
                currentMax = nums[i];
            else
                currentMax += nums[i];

            if (currentMax > max)
                max = currentMax;

        }
        return max;
    }
}

어차피 i=0일 때는 1자리 수 합 밖에 없고, 이것이 곧 currentMax이면서 max이므로 초기값을 세팅해놓고, for문을 1번부터 돌리는 것도 하나의 방법이다.

 

결과는 다음과 같다.

 

 

여기서 조금 더 깔끔하게 한다면 다음과 같이 할 수 있다.

public class MaximumSubarray {
    public int solution(int[] nums) {
        int currentMax = nums[0];
        int max = nums[0];
        int numsLength = nums.length;
        for (int i = 1; i < numsLength; i++) {
            currentMax = Math.max(nums[i], currentMax+nums[i]);
            max = Math.max(currentMax, max);
        }
        return max;
    }
}

결과는 다음과 같다.

성능이 조금 더 안나왔으며 메모리가 조금 더 사용량이 늘었는데, Java API를 사용하면 어쩔 수 없는 현상이다.

그리고 하드웨어 특성 상 같은 소스코드를 사용하더라도 컴파일 및 실행하는 pc의 환경이나 타이밍.. 에 따라 오차가 발생한다.

따라서 극강의 퍼포먼스를 위한 것이 아니라면 Java API를 사용해서 가독성을 높이도록 하자.