[어려운문제] max array sum
August 31, 2018 - [array, max-array-sum]
이웃하지 않은 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이 결과값이 된다.
그런데 이 문제를 어떻게 풀어야 할 지 도무지 아이디어가 떠오르지 않는다. 이런 저런 고민을 해보다가 시간관계상 보류.. (포기는 아직 아님.. 나중에라도 시간날 때 다시 들여다 볼 예정)
혹시 지나가다 이 문제 풀어보신 분 계시다면 조언을 바랍니다.