MaxDoubleSliceSum

문제

A non-empty array A consisting of N integers is given.

A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.

The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].

For example, array A such that:

    A[0] = 3

    A[1] = 2

    A[2] = 6

    A[3] = -1

    A[4] = 4

    A[5] = 5

    A[6] = -1

    A[7] = 2

contains the following example double slices:

• double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
• double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,
• double slice (3, 4, 5), sum is 0.

The goal is to find the maximal sum of any double slice.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, returns the maximal sum of any double slice.

For example, given:

    A[0] = 3

    A[1] = 2

    A[2] = 6

    A[3] = -1

    A[4] = 4

    A[5] = 5

    A[6] = -1

    A[7] = 2

the function should return 17, because no double slice of array A has a sum of greater than 17.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [3..100,000];
• each element of array A is an integer within the range [−10,000..10,000].

 

해설

정수 N개로 이루어진 배열 A와, x, y, z (0 <= x < y < z < N)가 주어졌을 때, A[x+1]부터 A[y-1]까지의 합과 A[y+1] ~ A[z-1] 까지의 합의 합이 최대가 되는 경우를 찾는 문제.

 

풀이

(x+1번째부터 y-1번째까지의 부분합) + (y+1번째부터 z-1번째까지의 부분합) 이 최대값이 되는 케이스를 찾아야하므로, 일단 두개의 부분합 배열이 필요하다.

// x+1 ~ y-1 부분합
int[] leftSum = new int[len];
initArr(leftSum);	// 배열 초기화(상세 코드 생략)

for (int i = 1; i < len; i++) {
	leftSum[i] = Math.max(leftSum[i-1] + A[i], 0);
}

// y+1 ~ z-1 부분합
int[] rightSum = new int[len];
initArr(rightSum);	// 배열 초기화(상세 코드 생략)
        
for (int i = len - 2; i > 0; i--) {
    rightSum[i] = Math.max(rightSum[i+1] + A[i], 0);
}

leftSum이 x+1~y-1번째까지의 부분합이되고,

rightSum이 y+1~z-1번째까지의 부분합이 됨.

 

두 배열에서 i는 y의 값을 나타낸다고 보면 됨.

 

부분합을 구할 때 Math.max의 역할이 중요함.

 

배열 A를 구성하는 정수들의 범위가 -10,000 ~ 10,000 이기때문에, 부분합이 음수 값이 되는 시점이 생길 수 있음

부분합이 음수다? 그러면 해당 구간의 부분합은 전체 부분합의 최대값을 떨어뜨리는 구간이 된다는 의미가 됨. 그럼 해당 구간을 버려야 한다는 의미로 0으로 초기화 해주는 것.

 

즉 leftSum을 기준으로 봤을 때, 0을 만나기전까지 x는 0이고, 0을 만나는 순간 x는 i가 된다고 보면 되지만, 구하고자하는 값이 x, y, z가 아니므로 크게 신경 안써도 됨

 

이제 y값(즉 배열의 i)를 옮겨가면서 두 배열의 합을 구하면 x+1~y-1, y+1~z-1 두 구간의 부분합이 구해지게 되며, 이를 이용해 최대값을 찾으면 된다.

 

for (int i = 1; i < len-1; i++) {
    int temp = leftSum[i-1] + rightSum[i+1];
    // System.out.printf("[%d] %d + %d = %d\n", i, leftSum[i-1], rightSum[i+1], temp);
    if (temp > sum) sum = temp;
}

 

 

 

소스

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // Implement your solution here
        int sum = 0;

        int len = A.length;

        if (len < 4) return sum;

        int[] leftSum = new int[len];
        initArr(leftSum);
        
        int[] rightSum = new int[len];
        initArr(rightSum);

        for (int i = 1; i < len; i++) {
            leftSum[i] = Math.max(leftSum[i-1] + A[i], 0);
        }

        // for (int left : leftSum) System.out.println(left);

        for (int i = len - 2; i > 0; i--) {
            rightSum[i] = Math.max(rightSum[i+1] + A[i], 0);
        }

        // for (int right : rightSum) System.out.println(right);

        for (int i = 1; i < len-1; i++) {
            int temp = leftSum[i-1] + rightSum[i+1];
            // System.out.printf("[%d] %d + %d = %d\n", i, leftSum[i-1], rightSum[i+1], temp);
            if (temp > sum) sum = temp;
        }


        return sum;
    }

    void initArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) arr[i] = 0;
    }

}