JavaScript 알고리즘: (arr[i] + arr[j]) + (i − j)의 최댓값 구하기

문제 소개

이번 문제는 정수로 이루어진 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성하는 것입니다.

함수는 배열에서 인덱스 쌍 (i, j)을 선택해야 하며, 이때 (arr[i] + arr[j]) + (i − j) 값이 가능한 모든 인덱스 쌍 중에서 가장 커야 합니다. 그리고 계산된 최댓값을 반환하면 됩니다.

예시

예를 들어 함수에 다음 배열을 입력한다고 가정해 보겠습니다.

const arr = [8, 1, 5, 2, 6];

이 경우 기대하는 출력은 다음과 같습니다.

const output = 11;

출력 설명

i = 0, j = 2를 선택하면 값은 다음과 같이 계산됩니다.

(8 + 5) + (0 - 2) = 11

어떤 인덱스 쌍을 골라도 이보다 큰 값을 만들 수 없으므로, 11이 정답이 됩니다.

구현 코드

이 문제를 해결하는 코드는 다음과 같습니다.

const arr = [8, 1, 5, 2, 6];
const findMaximum = (arr = []) => {
    let max = arr[0] + 0;
    let res = -Infinity;
    for(let i = 1; i < arr.length; i++){
        res = Math.max(res, max + arr[i] - i);
        max = Math.max(arr[i] + i, max);
    };
    return res;
};
console.log(findMaximum(arr));

코드 동작 원리

이 풀이의 핵심은 수식을 두 부분으로 분리하는 것입니다. 즉, (arr[i] + arr[j]) + (i − j)를 (arr[i] + i)와 (arr[j] − j) 형태로 나눌 수 있습니다.

배열을 왼쪽부터 순회하면서 각 위치 j에 대해, 그보다 앞선 인덱스들에서 등장한 (arr[i] + i)의 최댓값을 변수 max에 계속 갱신하여 유지합니다. 동시에 res에는 max + arr[j] − j 값 중 가장 큰 값을 저장합니다.

이렇게 하면 모든 인덱스 쌍을 일일이 비교하지 않고도 단 한 번의 순회(O(n))만으로 정답을 구할 수 있어 매우 효율적입니다.

출력 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

11