LeetCode 53: 부분 배열 합의 최대값 구하기 - Kadane's Algorithm 카데인 알고리즘 - 자바

문제 해석:

배열의 부분합(prefix sum)중 최대값을 구하는 문제.

배열의 최대 크기는 1 <= nums.length <= 105이며, 각 배열 안의 요소의 크기는 -104 <= nums[i] <= 104 으로 제약이 걸려있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

생각해야할 점:

반복문을 사용해 모든 부분 배열의 합을 구하게 되면 시간복잡도가 상당히 높아질 수 있으며 Time Limit Exceed 가 걸리게 됩니다.

부분 배열의 합을 어떻게 제일 스마트하게, 간단하게 구하여 비교할 것인지를 생각해야합니다.

풀이:

부분 합을 이용합을 이용해도 되지만, 이 문제의 경우 카데인 알고리즘으로도 쉽게 풀어낼 수 있습니다.

 

카데인 알고리즘:

위 문제의 예시 인풋을 이용한 풀이 입니다.

max 는 마지막에 리턴할 부분 배열합의 최대값을 리턴할 거고, sum 은 최대값과 비교해가며 계속 부분 배열의 합을 구한뒤 그값을 저장할 변수입니다.

sum 은 0으로 초기화 한 상태에서 시작하고, max 는 Integer.MIN_VALUE 로 초기화 한 상태에서 시작합니다.
sum에 해당 배열의 요소 값을 더한 뒤, 만약 sum이 max보다 큰 경우 max를 sum 값으로 만들어 줍니다.

첫번째 스탭의 경우 max는 인티저 중에 가장 작은 숫자이니 -2가 기존의 max 보다 클것이니 max는 -2가 됩니다.

sum 이 0 + (-2)로 음수가 나오는데 sum 이 0보다 작은 경우 sum 을 다시 0으로 만들어 줍니다.

이 과정을 반복하다 보면 마지막에 max = 6, sum = 5 로 남게 됩니다. 

 

이 카데인 알고리즘은 음수로만 이루어진 배열의 경우에도 사용이 가능합니다.

음수로만 이루어진 배열의 경우 최대 부분 배열의 합 = 음수들 중에 가장 큰 요소 입니다. 음수로만 이루어진 경우 배열을 합하면 합할 수록 숫자가 더 작아지기 때문에 그냥 그중 가장 큰 요소 하나를 뽑으면 되는데 sum 이 0보다 작은 경우 sum 을 다시 0으로 만들어 줍니다 

이부분을 보면 음수일 경우 sum은 계속 0으로 돌아가고 다음 합에서도 그냥 해당 배열의 요소값만 남게 됩니다.

그 결과를 max와 비교하니 결국 max에는 가장 큰 배열의 요소의 값이 남게됩니다. 

 

sum은 앞에서부터 배열을 계속 더해가며 그 값을 저장합니다. sum 이 max보다 클때 max 는 sum 의 값을 저장합니다.

지금까지 계산했던 부분 배열의 합 중에 가장 큰 것을 저장하고 있다가 리턴하는 형식입니다.

원리가 이해가 안된다면 max 값이 바뀔때의 배열과 그때의 인덱스 까지 몇개의 부분 배열이 나올 수 있는지를 생각하며 잘 살펴보도록 합시다.

 

 

슈도코드:

public class Solution {
    public static int maxSubArray(int[] nums) {
        sum = 0, max = 가장 작은 음수로 선언;

        for(배열의 길이만큼 반복){
            sum 에 배열의 요소를 하나씩 더한다;
            sum과 max를 비교 후,
            sum이 더 크다면 max 값을 sum의 값으로 업데이트한다;
            
            만약 sum이 0보다 작다면:
                sum을 0으로 초기화 해준다;
        }
        return max;
    }
}

코드(자바): 

public class Solution {
    public static int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE, sum = 0;

        for(int i=0;i<nums.length;i++){
            sum += nums[i];
            max = Math.max(sum,max);
            if(sum<0) {
                sum = 0;
            }
        }
        return max;
    }
}