[Java] 연속된 부분 배열의 최대 합 구하기

정수형 배열 num가 주어졌다. 연속된 부분 배열의 합 중 가장 큰 값을 출력하세요. 단, 구간의 최소 길이는 1입니다.

// 입출력 예시
nums: {-3, -2, 3, -1, 6, -7, 9, -4, 3}
출력: 10

 

 

O(n)의 시간복잡도로 문제를 해결하는 재미난 방법이 생각났다. 

 

nums[0]	nums[1]	nums[2]	nums[3]	nums[4]	nums[5]	nums[6]	nums[7]	nums[8]
-3	-2	3	-1	6	-7	9	-4	3

 

예시에서는 nums[2]부터 nums[6]까지의 합을 구했을 때가 최댓값이 된다. 그러면 2와 6이라는 인덱스를 어떻게 결정해야할지를 고민해야 한다. 

 

 

 

 

종료 인덱스 구하기

 

        int[] rightSum = new int[nums.length];
        int maxRight = Integer.MIN_VALUE;
        int maxRightIdx = -1;

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            rightSum[i] = sum;

            if (rightSum[i] >= maxRight) {
                maxRight = rightSum[i];
                maxRightIdx = i;
            }
        }

 

 

주어진 nums배열을 활용해서 nums[0]부터 nums[idx]까지의 부분합 데이터를 담은 배열(right방향)을 만들어준다.

 

nums[0]	nums[1]	nums[2]	nums[3]	nums[4]	nums[5]	nums[6]	nums[7]	nums[8]
-3	-2	3	-1	6	-7	9	-4	3

                                                                                       

↓

 

rightSum[0]	rightSum[1]	rightSum[2]	rightSum[3]	rightSum[4]	rightSum[5]	rightSum[6]	rightSum[7]	rightSum[8]
-3	-5	-2	-3	3	-4	5	1	4

 

0부터 Idx까지의 합을 구했을 때의 최댓값은 rightSum[6]인 5 이다. 즉, 부분 배열에서 nums[7]과 nums[8]이 포함되는 순간 부분 배열의 합은 nums[6]까지 더했을 때 보다 작아지게 된다. 즉, 아직 시작 지점은 모르겠지만 최대 합을 구하기 위해서는 시작 인덱스부터 nums[6]까지 더해야한다.

 

 

 

 

 

 

시작 인덱스 구하기

 

        int[] leftSum = new int[nums.length];
        int maxLeft = Integer.MIN_VALUE;
        int maxLeftIdx = -1;

        sum = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            sum += nums[i];
            leftSum[i] = sum;

            if (leftSum[i] >= maxLeft) {
                maxLeft = leftSum[i];
                maxLeftIdx = i;
            }
        }

 

시작 지점은 종료 지점과 반대로 구해준다. nums[nums.length - 1]부터 nums[idx]까지의 부분합을 담은 배열 (left방향)을 만들어준다.

 

nums[0]	nums[1]	nums[2]	nums[3]	nums[4]	nums[5]	nums[6]	nums[7]	nums[8]
-3	-2	3	-1	6	-7	9	-4	3

                                                                                       

↓

 

 

leftSum[0]	leftSum[1]	leftSum[2]	leftSum[3]	leftSum[4]	leftSum[5]	leftSum[6]	leftSum[7]	leftSum[8]
4	7	9	6	7	1	8	-1	3

 

nums[nums.length - 1] 부터 nums[idx] 까지의 합을 구했을 때의 최댓값은 leftSum[2]인 9 이다. 마찬가지로 연속된 부분 배열에서 nums[0]과 nums[1]이 포함되는 순간 부분 배열의 합은 종료지점부터 nums[2]까지 더했을 때 보다 작아지게 된다. 즉, 시작 지점을 nums[2]로 정해야 최대 합을 구할 수 있다.

 

 

 

 

 

최대 구간의 합 구하기

 

        int maxSum = 0;
        if (maxRightIdx > maxLeftIdx) {
            for (int i = maxLeftIdx; i <= maxRightIdx; i++) {
                maxSum += nums[i];
            }
        } else {
            maxSum = IntStream.of(nums).max().getAsInt();
        }

 

시작 지점과 종료 지점을 구했는데, 예외 처리를 해줘야 하는 부분이 있다. 이때까지 구한 것은 종료 인덱스가 시작 인덱스보다 큰, 최대 구간의 길이가 2 이상인 경우이다. 즉 종료인덱스가 정상적으로 시작 인덱스보다 크다면 간단하게 for문으로 maxSum을 구해주면 된다.

 

하지만 배열이 모두 음수인 경우는 어떨까? 어느 구간을 구하더라도 구간의 길이가 1인 경우보다는 합이 작아지게 된다. 즉, maxRightIdx와 maxLeftIdx가 정상적으로 작동하지 않게 된다. 따라서 종료시점이 시작지점과 작거나 같은 경우 배열에서 가장 큰 수를(구간의 길이: 1) maxSum으로 지정한다.

 

 

 

 

 

 

 

전체 코드

 

import java.util.stream.IntStream;

class PartialSum {
    public int partialSum(int[] nums) {
    
    	// 배열의 길이가 1일 경우의 예외처리
        if (nums.length == 1) {
            return nums[0];
        }
		
        
        // 종료 인덱스 구하기
        int[] rightSum = new int[nums.length];
        int maxRight = Integer.MIN_VALUE;
        int maxRightIdx = -1;

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            rightSum[i] = sum;

            if (rightSum[i] >= maxRight) {
                maxRight = rightSum[i];
                maxRightIdx = i;
            }
        }
		
        
        // 시작 인덱스 구하기
        int[] leftSum = new int[nums.length];
        int maxLeft = Integer.MIN_VALUE;
        int maxLeftIdx = -1;

        sum = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            sum += nums[i];
            leftSum[i] = sum;

            if (leftSum[i] >= maxLeft) {
                maxLeft = leftSum[i];
                maxLeftIdx = i;
            }
        }


        // 구간의 합 구하기
        int maxSum = 0;
        if (maxRightIdx > maxLeftIdx) {
            for (int i = maxLeftIdx; i <= maxRightIdx; i++) {
                maxSum += nums[i];
            }
        } else {
            maxSum = IntStream.of(nums).max().getAsInt();
        }

        return maxSum;
    }
}

class Main {
    public static void main(String[] args) {
        PartialSum p = new PartialSum();
        System.out.println(p.partialSum(new int[]{-3, -2, 3, -1, 6, -7, 9, -4, 3}));
    }
}