[DynamicProgramming] HackerRank Algorithms in Java ‘Max Array Sum’ solution

Problem

Given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset.

For example, given an array arr = [-2,1,3,-4,5] we have the following possible subsets:

Subset	Sum
[-2, 3, 5]	6
[-2, 3]	1
[-2, -4]	-6
[-2, 5]	3
[1, -4]	-3
[1, 5]	6
[3, 5]	8

Our maximum subset sum is 8.

Sample Input 0

5
3 7 4 6 5

Sample Output 0

13

Solution

현재 위치 i번째 값을 더하는 방법과 더하지 않고 건너 뛰는 방법이 있다.

• 바로 두칸 뒤에 있는 수와 부분 수열을 만들거나 세칸 뒤에 있는 수와 부분 수열을 만들 수 있다. 둘 중 가장 큰 수를 선택한다.
• 현재 값이 음수이면 더해도 최고값이 나올 수 없으므로 건너뛴다.
• 현재 값과, 이전 값과 현재 값을 더한 결과 중 큰 결과를 저장한다.
• dp배열의 마지막이 항상 최대 값이 나오는 것은 아니다. (이전 단계에서 최대값이 나왔을 수도 있다. 부분 수열의 길이가 반드시 길어야 하는 것은 아니므로) 따라서 최대값을 저장해주어야 한다.

Code

    // Complete the maxSubsetSum function below.
    static int maxSubsetSum(int[] arr) {
        int max = 0;
        
        int[] dp = new int[arr.length + 1];
        dp[0] = 0; dp[1] = arr[0]; dp[2] = arr[1];
        for(int i = 3; i <= arr.length; i++) {
            int tmp = Math.max(dp[i-2], dp[i-3]);
            if(0 <= arr[i-1]) dp[i] = Math.max(arr[i-1], tmp + arr[i-1]);
            else dp[i] = tmp;
            
            max = Math.max(max, dp[i]);
        }
        return max;
    }