이웃하지 않은 2개 이상의 요소로 이루어진 부분집합 중 요소의 합계가 가장 큰 값을 구하는 문제 https://www.hackerrank.com/challenges/max-array-sum/problem

예를 들어 [-2,1,3,-4,5] 가 입력으로 주어진다면 이웃하지 않은 subset 과 subset별 합계는 아래와 같다

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

이 경우 subset 합계들의 최대값 8이 결과값이 된다.

그런데 이 문제를 어떻게 풀어야 할 지 도무지 아이디어가 떠오르지 않는다. 이런 저런 고민을 해보다가 시간관계상 보류.. (포기는 아직 아님.. 나중에라도 시간날 때 다시 들여다 볼 예정)

혹시 지나가다 이 문제 풀어보신 분 계시다면 조언을 바랍니다.