MaxDoubleSliceSum (Codility) - Java

문제

N개의 숫자를 원소로 가지고 배열 A가 주어진다. 여기서 (X, Y, Z) 인덱스 위치가 주어진다. (0 <= X < Y < Z < N)  이 인덱스위치의 Sum of Double Slice 값은 A[X + 1] + A[X + 2] + ... + A[Y - 1] + A[Y + 1] + ... + A[Z - 1] 이다. 이 값이 가장 큰 인덱스 위치의 Sum of Double Slice를 구하는 문제이다.

 

X ~ Y 인덱스 위치 사이의 값들의 합과 Y ~ Z 인덱스 위치 사이의 값들의 합을 더한 값이 최종 Sum of Double Slice 값이 된다. 만약 X, Y, Z가 1만큼씩 떨어져 있다면 인덱스 범위 사이에서 더할 값이 없기 때문에 Sum of Double Slice 값은 0이 된다.  

 

해결방법

그냥 루프문을 사용하여 모든 X, Y, Z의 경우를 구해보는 방법은 엄청나게 비효율적이다. 루프문이 3번 중첩되어야 하므로 시간 복잡도는 O(N^3)이 될것이다. 

 

우선 X, Y, Z 인덱스 위치의 값들은 덧셈에 포함하지 않으므로, X의 최소값인 0과 Z의 최대값인 N - 1은 연산에 포함시킬 필요가 없다. 

 

위치에 따라 알맞은 부분 합들을 미리 배열에 준비해놓는다. 그리고 그 배열을 알맞게 채운 후 Y 위치를 옮겨가면서 큰 부분합이 무엇인지 배열에서 찾아 더해주면 답을 쉽게 구할 수 있다.

 

예를 들면 다음과 같다.

번째 : 0  1  2   3  4  5   6  7
숫자 : 3  2  6  -1  4  5  -1  2

우선 덧셈에 포함되지 않을 0번째 3과 N-1번째 2는 제외 시킨다.
번째 : 0  1  2   3  4  5   6  7
숫자 : X  2  6  -1  4  5  -1  X

X의 범위 : 0 ~ 5
Y의 범위 : 1 ~ 6
Z의 범위 : 2 ~ 7

부분합 기록을 위한 배열 M, N을 선언한다.
X~Y의 부분합 : M[0 ~ 7] (0으로 초기화)
Y~Z의 부분합 : N[0 ~ 7] (0으로 초기화)

M[1] = 2
N[7 - 1] = -1

이제 2부터 5까지 순회를 돌며 부분합을 구한다.
음수값이 더해져 부분합이 기존 위치 값보다 더 작아지는 경우를 max로 검사한다. 
* 2일때 
M[2] = max((M[1] + A[2]), A[2])
N[(7 - 1) - 2] = max((N[(7 - 1) - 1] + A[[(7 - 1) - 2]), A[[(7 - 1) - 2])

* 3일때
M[3] = max((M[2] + A[3]), A[3])
N[(7 - 1) - 3] = max((N[(7 - 1) - 2] + A[[(7 - 1) - 3]), A[[(7 - 1) - 3])

...

* 5일때
M[5] = max((M[4] + A[5]) or A[5])
N[(7 - 1) - 5] = max((N[(7 - 1) - 4] + A[[(7 - 1) - 5]), A[[(7 - 1) - 5])

이제 M, N 부분합 정보를 바탕으로 Y를 이동시키면서 그 상황에서의 최대 부분합을 구한다.
하지만 최대 부분합이 음수일 경우는 max 검사를 통해 0으로 만들어 준다.
(가장 근접하게 인덱스 위치를 정해주면 그 부분합은 무조건 0이기 때문이다.)

Y -> 1일 경우
max(0, M[1 - 1]) + max(0, N[1 + 1])

Y -> 2일 경우
max(0, M[2 - 1]) + max(0, N[2 + 1])

...

Y -> 6일 경우
max(0, M[6 - 1]) + max(0, N[6 + 1])

이 값들중 가장 큰 값이 정답이 된다.

코드는 다음과 같다. for문을 중첩하여 사용하지 않았기 때문에 시간 복잡도는 O(N)이 된다.

class Info{
	int sum_from_front = 0;
	int sum_from_back = 0;
}

class MaxDoubleSliceSum {
	public int solution(int[] A) {
		if (A == null || A.length == 3) {
			return 0;
		}
		
		Info[] infos = new Info[A.length];
		for(int i = 0; i < infos.length; ++i) {
			infos[i] = new Info();
		}
		
		infos[1].sum_from_front = A[1];
		infos[A.length - 2].sum_from_back = A[A.length - 2];
		for (int i = 2; i < infos.length - 2; ++i) {
			infos[i].sum_from_front = Math.max(A[i], 
					infos[i - 1].sum_from_front + A[i]);

			int backIndex = A.length - i - 1;
			infos[backIndex].sum_from_back = Math.max(A[backIndex], 
					infos[backIndex + 1].sum_from_back + A[backIndex]);
		}
		
		int maxSlice = 0;
		for(int i = 0 ; i < A.length - 2; ++i) {
			int partSumFromFront = Math.max(0,  infos[i].sum_from_front);
			int partSumFromBack = Math.max(0, infos[i + 2].sum_from_back);
			int sum = partSumFromFront + partSumFromBack;
			
			maxSlice = Math.max(maxSlice, sum);
		}
		return maxSlice;
	}
}