[해커랭크 HackerRank] DP 알고리즘 Max Array Sum

문제

자연수 행렬이 주어질 때, 비인접하는 원소의 행렬들을 구하고, 그원소들의 최대합을 구하라.
예를 들어, arr = [-2, 1, 3, -4, 5] 라는 행렬이 주어졌을 때 존재할 수 있는 비인접 원소 행렬들은 아래와 같다.

SUBSET  |  합
[-2, 3, 5]    6
[-2, 3]        1
[-2, -4]     -6
[-2, 5]        3
[1, -4]       -3
[1, 5]          6
[3, 5]          8

[3, 5] 행렬이 가장 큰 합인 8을 가지므로, 8을 return 한다.

---

 

풀이

 

k번째 원소를 포함하고 있는 비인접행렬은 아래의 경우들이다.

 

(A) k-2번째에 존재할 수 있는 모든 비인접행렬에 arr[k]를 더해준 것

    tip: 최대합을 구하는 문제이므로 단순히 k-2번째에 존재하는 비인접행렬의 최댓값에 arr[k]를 더해주면 그게 k번째의 새 최대값이 될 것이다. arr[k]가 음수라면 최댓값이 작아지므로 arr[k-2]를 계속 최댓값으로 가져가면 된다.

 

(B) k-2까지의 모든 원소와 arr[k]의 조합
    ex. (arr[1], arr[k]), (arr[2], arr[k]), ..., (arr[k-2], arr[k])

 

A의 최댓값과 B의 최댓값을 비교하여 최댓값을 채택한다.

 

---

 

 

 

Python3 코드

import collections

def maxSubsetSum(arr):
    if len(arr) < 3:
        return 0
    elif len(arr) ==3:
        return arr[0]+arr[2]

    max_arr = sortArray(arr)
    max_index = max(max_arr[0]+arr[2], max_arr[1]+arr[3])
    queue = collections.deque([max_arr[0]+arr[2], max_arr[1]+arr[3]])

    for i in range(4, len(arr)):
        q = queue.popleft()
        current = max(q, max_arr[i-2]) + arr[i]
        if max_index < current:
            max_index = current
        queue.append(max_index)
    return max_index


def sortArray(arr):
    max_arr = [arr[0]]
    for i in range(1, len(arr)):
        if max_arr[i - 1] < arr[i]:
            max_arr.append(arr[i])
        else:
            max_arr.append(max_arr[i - 1])
    return max_arr

* 큐에 k-2, k-1번째 최댓값을 순서대로 넣고 leftpop으로 꺼내서 arr[k]을 더해서 (양수일경우) 다시 큐에 집어넣는 방식을 택했다.

# test case

test1 = [-2, 1, 3, -4, 5]

maxSubsetSum(test1)
# expected: 8