[HackerRank] Max Array Sum

Max Array Sum은 배열에서 인접하지 않은 원소들의 합 중 최대가 되는 값을 구하는 문제이다.

여기서 인접하지 않는다는 말은 임의의 인덱스 i, j 값이 i != j + 1 or i != j - 1일 경우를 말한다.

문제를 이해하기 쉽게 배열을 그려보았다.

 

위의 배열 그림에서 연두색이 기준이 되는 인덱스라 가정한다(맨 위의 그림에서 3번 인덱스 색). 

각각의 경우에서 최소 -2만큼 떨어져 있는 인덱스를 더할 수 있으며 위에서 부터

[2, 0], [3, 0], [3, 1], [4, 2], [4, 2, 0], [4, 1], [4, 0] 의 경우가 가능하다. 

brute force를 통해 문제를 푼다면 3중 for문이 필요할 것이다. O(n^3)이 되므로 많은 경우에 효율적인 알고리즘이라고 보기 힘들 것이다.

문제의 규칙을 정의해보자.

 

해당 문제의 규칙을 만들어 보자.

• 규칙 1. 양수의 경우 더하는 것이 무조건 유리하다. (음수는 더하면 무조건 분리하다.)
• 규칙 2. 임의의 인덱스 i에 최소 2 만큼 떨어져 있는 수만 더할 수 있다.

위의 규칙을 적용하여 각각의 인덱스에서 최대값을 구하면 다음과 같을 것이다.

각각의 인덱스에서 최대값은 i -2 인덱스와 i - 3인덱스의 최대 값을 포함합니다. 위의 규칙을 이용하여 소스코드를 작성하면 다음과 같다.

public class Main {
    static int maxSubsetSum(int[] arr) {
        int n = arr.length;

        if (n == 1) {
            return arr[0];
        } else if (n == 2) {
            return Math.max(arr[0], arr[1]);
        }

        int[] memo = new int[n + 1];
        memo[0] = -100000;
        memo[1] = arr[0];
        memo[2] = arr[1];
        int max = -100000;
        for (int i = 2; i < n; i++) {
            int memoMax = Math.max(memo[i - 1], memo[i - 2]);
            if (arr[i] >= 0) {
                memo[i + 1] = Math.max(memoMax + arr[i], arr[i]);
            } else {
                memo[i + 1] = memoMax;
            }
            max = Math.max(max, memo[i + 1]);
        }
        return max;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }

        int res = maxSubsetSum(arr);

        bufferedWriter.write(String.valueOf(res));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}