[Hackerrank] [Medium] Max Array Sum

https://www.hackerrank.com/challenges/max-array-sum/problem

Max Array Sum | HackerRank

풀이

• 입력으로 정수로 구성된 arr를 받을 때, 이웃하지 않은 element와의 최대합을 구하는 문제
• n1, n2, n3 3개만 있고 swap해가면서 정답을 구할 수 있음.
• 보통 dp[i] = i번째 원소까지 봤을 때 최대합 으로 생각해 문제를 접근
  • n2를 초기화할 때 arr[1]로 하지 말고 max(2번째 원소까지)
  • 음수 값도 존재하기 때문에, i번째 원소가 최대인 경우도 있음.
    • max 값을 update할 때 자기 자신이 최대인 경우도 생각해야 함.

def maxSubsetSum(arr):
    if len(arr) == 1:
        return arr[0]
    n1, n2 = arr[0], max(arr[:2])
    for a in arr[2:]:
        n3 = max(n2, n1+a, a)
        n1, n2 = n2, n3
    return n3