[코딜리티] codility lesson 9 Maximum slice problem - MaxDoubleSliceSum 100%

문제 요약.
https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/
배열을 세번 잘라내어 더했을 때 가장 높은 값을 찾으시오.

원문.

A non-empty zero-indexed 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:

int solution(int A[], int N);

that, given a non-empty zero-indexed 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.

Assume that:

• 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].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

중요부분 요약
이 배열의 인덱스는 0부터 시작하며 비어있지 않은 N개의 인티저 로 구성되어 있습니다.
배열을 세번 (X, Y, Z) 잘라서 4조각으로 만드는걸 Double Slice 라고 합니다.
Double Slice 의 합은 앞뒤 맨끝을 빼버리고, 가운데 있는 두 조각의 합을 말합니다.


예를 들어. 다음과 같은 배열이라고 하면
A[0] = 3 A[1] = 2 A[2] = 6 A[3] = -1 A[4] = 4 A[5] = 5 A[6] = -1 A[7] = 2

equi leader 는 두개가 됩니다.

• 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.

(0,3,6) 으로 잘랐을 경우에는
A[0] = 3 X A[1] = 2 A[2] = 6 A[3] = -1 Y A[4] = 4 A[5] = 5 A[6] = -1 Z A[7] = 2
 이중에 x와 z 사이의 값을 덧셈 합니다.

함수의 정의 는 이렇습니다.
int solution(int A[], int N);


주의

• N 의 범위는 [3..100,000];
• 배열 원소의 범위는 [−10,000..10,000].

복잡도

• 최악의 시간복잡도는 O(N);
• 최악의 공간복잡도는 O(N), 입력인수의 저장공간은 계산하지 않음.

풀이.
먼저 배열을 둘로 쪼개는 알고리즘을 만듭니다. 그리고 그걸 두번 더 합니다.

class Solution { public int solution(int[] A) { // write your code in Java SE 8 if(A.length == 3) return 0; //원소가 3개면 그냥 끝내기 int sliceX = 0, sliceY = 0, sliceZ = A.length-1; int pointer = 1, sliceOne = 0, sliceTwo = 0; int total = 0; for( ; pointer < sliceZ ; pointer++) { total += A[pointer]; } //전체합 계산 int getMAX = total, subsum = total; sliceOne = pointer--; for( ; pointer > sliceX+1 ; pointer--){ //오른쪽 슬라이스 찾기 subsum = subsum - A[pointer]; if(getMAX < subsum ){ getMAX = subsum; sliceOne = pointer; } } getMAX = total; subsum = total; sliceTwo = 0; for( ; pointer < sliceZ-1 ; pointer++){ //왼쪽 슬라이스 찾기 subsum = subsum - A[pointer]; if(getMAX < subsum ){ getMAX = subsum; sliceTwo = pointer; } } sliceZ = (sliceOne > sliceTwo ) ? sliceOne : sliceTwo; sliceX = (sliceOne < sliceTwo ) ? sliceOne : sliceTwo; // System.out.println(sliceX+","+sliceZ); //두개의 슬라이스 찾음 subsum = 0; pointer = 0; for(; pointer < sliceZ ; pointer++) { subsum += A[pointer]; } //왼편합 계산 subsum=subsum-A[sliceX]; getMAX = subsum; pointer = 0; if(sliceX==pointer){getMAX = subsum - A[pointer];pointer++;} for(; pointer < sliceX ; pointer++){ //왼편 최대값찾기 subsum = subsum - A[pointer]; if(getMAX < subsum){getMAX = subsum; sliceY = pointer;} } subsum = 0; pointer = A.length-1; for(; pointer > sliceX ; pointer--) { subsum += A[pointer]; } //오른편합 계산 subsum=subsum-A[sliceZ];pointer = A.length-1; if(sliceZ==pointer){getMAX = subsum - A[pointer];pointer--;} for(pointer = A.length-1; pointer > sliceZ ; pointer--){ //오른편 최대값찾기 subsum = subsum - A[pointer]; if(getMAX < subsum){getMAX = subsum;sliceY = pointer;} } subsum = 0; pointer = sliceX+1; for(; pointer < sliceZ ; pointer++) { subsum += A[pointer]; } //중간합 계산 if(sliceZ-sliceX > 2){getMAX = subsum - A[sliceX+1];} for( pointer = sliceX+1; pointer < sliceZ ; pointer++){ //중간 최대값찾기 if(getMAX < subsum - A[pointer]){ getMAX = subsum - A[pointer]; sliceY = pointer; } } // System.out.println(getMAX+","+subsum+","+sliceX+","+sliceY+","+sliceZ); return getMAX; //두개더하기 } }

[3, 2, 6, -1, 4, 5, -1, 2]

[-2, -3, -4, 1, -5, -6, -7]
[6, 1, 5, 6, 4, 2, 9, 4]
[0, 10, -5, -2, 0]
[-8, 10, 20, -5, -7, -4]
[-8, 10, 20, -5, -7, -4]