Codility Lesson9 - MaxDoubleSliceSum

🔍 문제

---

 

MaxDoubleSliceSum coding task - Learn to Code - Codility

 

✏️ 풀이

---

부분합 구하기 문제를 꼬아서 낸 문제이다. 부분합 구하기 문제는 아래 링크로 가면된다.
👉 Codility Lesson9 - MaxSliceSum

 

주어진 배열 A를 예를 들면 0번 인덱스와 7번 인덱스는 어떠한 경우에도 포함되지 않는다. 따라서 인덱스 1번과 6번 사이에서 가능한 최대 부분합을 구하면되는데, (X,Y,Z)에서 Y 인덱스 값은 부분합에 포함되지 않아야 한다.

 

따라서 Y를 기준으로 앞쪽으로 부분합 배열을 하나 만들고, 뒷쪽으로 부분합 배열을 하나 만들어서 두 배열을 합한 값이 가장 큰 값을 return하면 된다.

Math.max(0, value)처럼 0과 비교해 주는 이유는, X,Y가 인접한 경우와 Y,Z가 인접한 경우 값이 0이므로 값으로 넣을 수 있는 가장 작은 값이다. 따라서 0과 이전 인덱스 까지의 최대 부분합 + 현재 인덱스 값과 비교해서 더 큰 값을 넣어준다.

마지막 두 배열을 합치는 부분에서 인덱스 Y값을 제외하고 더해야한다는 것을 깜빡하고 대체 왜 값이 다르게 나오는지 찾느라 진짜로 하루종일 걸렸다. 후... 어쨌든 그래도 찾아서 다행이다. 이제 두 발 뻗고 잘 수 있을 것 같아... 성불합니다...

function solution(A) {
    const N = A.length;

    if(N === 3) return 0;

    let headSum = A.map(i => 0);
    let tailSum = A.map(i => 0);

    for(let i = 1; i < N-1; i++) {
        headSum[i] = Math.max(0, headSum[i-1] + A[i]);
    }

    for(let i = N-2; i >= 1; i--) {
        tailSum[i] = Math.max(0, tailSum[i+1] + A[i]);
    }

    let maxSum = 0;

    for(let i = 1; i < N-1; i++) {
        maxSum = Math.max(maxSum, headSum[i-1] + tailSum[i+1]);    
    } 

    return maxSum;
}