Codility Java MaxDoubleSliceSum
업데이트:
문제
코드
// 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) {
int result = 0;
// Init subsum arrays.
int[] firstSubSum = new int[A.length];
for (int idx = 1; idx < A.length - 1; idx++) {
firstSubSum[idx] = Math.max(0, firstSubSum[idx - 1] + A[idx]);
}
int[] secondSubSum = new int[A.length];
for (int idx = A.length - 2; idx >= 1; idx--) {
secondSubSum[idx] = Math.max(0, secondSubSum[idx + 1] + A[idx]);
}
// Calculate max(result) value.
for (int idx = 1; idx < A.length - 1; idx++) {
int temp = firstSubSum[idx - 1] + secondSubSum[idx + 1];
if (temp > result) {
result = temp;
}
}
return result;
}
}
설명
- 세 인덱스 사잇 값들을 더한 값을 보관하기 2개의 배열 firstSubSum, secondSubSum을 생성하여 반복문을 통해 계산한다.
- 반복의 초기 값은 배열의 처음과 마지막 값을 빼고 계산해야 하기 때문에 0과 A.length - 1의 값은 제외한다.
- firstSubSum 계산은 정방향으로, secondSubSum 계산은 역방향으로 누적합계를 구한다.
- 특정 인덱스가 주어지면, 해당 인덱스 기준으로 사잇 값의 누계를 합하여 주어진 문제의 결과로 반환한다.
결과
소스
Sample Code는 여기에서 확인 가능합니다.
댓글남기기