Max Array Sum 풀이 Java

 

Max Array Sum | HackerRank

 

 

DP문제

subset of non-adjacent elements : 인접하지 않은 요소들의 집합

 

arr = {-2, 1, 3, -4, 5}

dp = new int[5]

 

시작하기 전에, dp[0] = -2 (제일 첫번째 수만 초기화)

dp[1] = max(n,d(n-1)) = max(-2,1) = 1

 

case 1 : N번째 수를 포함하는 경우

n : n 번째 값, d(n) : n 까지의 합

 

max(n,d(n-2)+n) 

* d(n-2)인 이유는 인접하면 안되기 때문

 

case 2 : N번째 수를 포함하지 않는 경우

d(n-1)

 

----

d[n] = max(n,d(n-2)+n,d(n-1)) 

 

 

* 문제 이해 잘 해야하는 부분

arr = [-2, -3, -1] In this case, it is best to choose no element: return 0.

-> 여기서 알 수 있는건 subset을 뽑을 때 아무것도 안뽑는게 가능하다.

-> 결과가 음수라면 0으로 변경 (그런데 이 조건 안넣어도 케이스는 다 통과함)

 

These exclude the empty subset and single element subsets which are also valid.

-> 비어있는 subset이나 1개만 선택한 경우도 가능하다.

 

그러니까 arr = [-2, 1, 3] 이면 가능한 경우는

[],[-2],[1],[3],[-2,3] 이다.

 

 

public class DP_1 {

	// Complete the maxSubsetSum function below.
	static int maxSubsetSum(int[] arr) {
        int size = arr.length;

        int[] max = new int[size];

        max[0] = arr[0];
        max[1] = Math.max(arr[1], arr[0]);
        for (int i = 2; i < arr.length; i++) {
            int m = Math.max(arr[i], arr[i] + max[i - 2]);
            m = Math.max(m, max[i - 1]);

            max[i] = m;
        }
        
        int res = max[size-1]<0 ? 0 : max[size-1];
        
        return res;
    }

	public static void main(String[] args) {

		int[] arr = { -2, 1, 3, -4, 5 };

		int res = maxSubsetSum(arr);
		System.out.println(res);

	}
}