As an input i'm given an array of integers (all positive). Also as an input i`m given a number of "actions". As an "action" i can either:

1. Add current element to sum
2. Move to the next element

We are starting at 0 position in array. Each element could be added only once. Limitation are:

1. 2 < array.Length < 20
2. 0 < number of "actions" < 20

It seems to me that this limitations essentially not important. Its possible to find each combination of "actions", but in this case complexity would be like 2^"actions" and this is bad...))

Examples:

array = [1, 4, 2], 3 actions. Output should be 5. In this case we added zero element, moved to first element, added first element.

array = [7, 8, 9], 2 actions. Output should be 8. In this case we moved to the first element, then added first element.

Could anyone please explain me the algorithm to solve this problem? Or at least the direction in which i shoudl try to solve it.

Thanks in advance

CodePudding user response：

array = [1, 1, 1, 1, 100]
actions = 5

In example like above, you just have to keep moving right and finally pickup the 100. At the beginning of the array we never know what values we are going to see further. So, this can't be greedy.

You have two actions and you have to try out both because you don't know which to apply when.

Below is a python code. If not familiar treat as pseudocode or feel free to convert to language of your choice. We recursively try both actions until we run out of actions or we reach the end of the input array.

def getMaxSum(current_index, actions_left, current_sum):
    nonlocal max_sum
    if actions_left == 0 or current_index == len(array):
        max_sum = max(max_sum, current_sum)
        return 

    if actions_left == 1:
        #Add current element to sum
        getMaxSum(current_index, actions_left - 1, current_sum   array[current_index])
    else:
        #Add current element to sum and Move to the next element
        getMaxSum(current_index   1, actions_left - 2, current_sum   array[current_index])

    #Move to the next element
    getMaxSum(current_index   1, actions_left - 1, current_sum)
    
array = [7, 8, 9]
actions = 2
max_sum = 0

getMaxSum(0, actions, 0)
print(max_sum)

You will realize that there can be overlapping sub-problems here and we can avoid those repetitive computations by memoizing/caching the results to the sub-problems. I leave that task to you as an exercise. Basically, this is Dynamic Programming problem.

Hope it helped. Post in comments if any doubts.

CodePudding user response：

Indeed, there is a greedy solution and there is no need for DP here.

With a budget of n actions, if we take x numbers, we can reach at most n-x-1th number. Common sense: it makes sense to take only the top numbers. Solution: iterate to n-1th number, maintain a heap of top x.

def getMaxSum(data, action_budget=None):
    action_budget = action_budget or len(data)

    start_idx = (action_budget   1) // 2
    heap = data[:start_idx]
    heapq.heapify(heap)
    best_heap = heap.copy()
    best_sum = sum(heap)

    for position in range(start_idx, min(action_budget, len(data))):
        new_sum = best_sum   data[position]
        heapq.heappush(heap, data[position])
        while len(heap) > action_budget - position:
            new_sum -= heapq.heappop(heap)
        if new_sum > best_sum:
            best_sum = new_sum
            best_heap = heap.copy()

    return best_heap

Overall complexity is O(n log n)