Finding max sum according to rule

Question

I have to find maximum sum of elements in integer array, according to the rule:

If second (or any consecutive) element is added to the sum - only half of the value is added. To avoid this, you can skip one elememnt.

For example we have an input like this [4, 2, 5, 1, 5] The result should be 14. In this case, we took elements at 0, 2 and 4 positions (4 + 5 + 5 = 14), and skipped elements at positions 1 and 3

The other example would be input like [3, 1, 10, 6, 3, 10] In this case the answer should be 26. We took elements at positions 0, 2, 3, 5 and skipped elements at positions 1 and 4. Therefore sum counts as:

3 + 0 + 10 + 6/2 + 0 + 10 = 26

Could anyone please explain me the algorithm to solve this problem? Or at least the direction in which i shoudl try to solve it. Does this task has anything to do with dynamic programming? Or maybe with recursion?

Thanks in advance

Answer 1

A simple optimum solution is to iteratively calculate two sums, both corresponding to a maximum up to the current index i, the first sum (sum0) assuming current value arr[i] is not used, the second sum (sum1) assuming the current value arr[i] is used.

    sum0_new = max (sum0, sum1);
    sum1_new = max (sum0 + x, sum1 + x/2);
    

Complexity: O(N)

Code:

This is a simple C++ code to illustrate the algorithm.
This implementation assumes integer division par 2. Easy to modify if it is not the case.

Output: 14 26

#include <iostream>
#include <vector>
#include <algorithm>

int max_sum (const std::vector<int>& arr) {
    int sum0 = 0; 
    int sum1 = 0; 
    for (int x: arr) {
        int temp = sum0;
        sum0 = std::max (sum0, sum1);
        sum1 = std::max (temp + x, sum1 + x/2);
    }
    return std::max (sum0, sum1);
}

int main() {
    std::vector<std::vector<int>> examples = {
        {4, 2, 5, 1, 5},
        {3, 1, 10, 6, 3, 10}
    };
    for (std::vector<int>& arr: examples) {
        int sum = max_sum (arr);
        std::cout << sum << '\n';
    }
    return 0;
}