Find the best way to get the max sum in a list where sum of three consecutive elements is not allowed

Question

I am trying to find a maximum sum of elements in a list where the sum of three consecutive elements is not allowed. So, to find the max sum, you'll have to go through each element sequentially from the first element of the list(Must have first element value in max sum output). You can not select more than two elements in a row.

So, the simple example will be like this:

Input: list = [1, 2, 3, 4, 5]

Possible combination of elements might be like this:

1 = [1, 2, 4, 5] & Sum of elements : 12

2 = [1, 3, 5] & Sum of elements: 9

Output: 12 (Elements used to calculate maximum sum: [1, 2, 4, 5])

Rules followed:

1. A must selection of first element of the list.

2. Traverse through list sequentially.

3. Can not select more than two elements in a row.(Here in this scenario, selected first two element which is 1 & 2, then skip 3 and choose 4 & 5)

And I have got the solution, but I would like suggestions on how to make it more efficient.

These are the details of the problem:

Input format

Line 1: A single integer N, the number of elements.

Line 2: List of elements.

Output format

The output consists of a maximum sum of elements

Sample Input: 1

5

[10, 3, 5, 7, 3]

Sample Output: 1

23

(Explanation: 10+3+7+3)

Sample Input: 2

8

[3, 2, 3, 2, 3, 5, 1, 3]

Sample Output: 2

17

(Explanation: 3+3+3+5+3)

Sample Input: 3

5

[10, 1, 5, 7, 3]

Sample Output: 3

22

(Explanation: 10+5+7)

Now, for this problem, I have managed to provide a solution, which is this one

def get_max_sum(num, input):
    output_1 = {'skip': True, 'sum': input[0]+input[1], 0: input[0], 1:input[1]}
    output_2 = {'skip': False, 'sum': input[0]+input[2], 0: input[0], 2:input[2]}

    main_output = [output_1, output_2]

    for i in range(2, num):
        for output in main_output:
            if output.get(i) is None:
                if output['skip']:
                    output['skip'] = False
                    continue
                if len(input) > i+1:
                    if input[i] > input[i+1] or output.get(i-1) is None:
                        output[i] = input[i]
                        output['sum'] += input[i]
                        if output.get(i-1) is not None:
                            output['skip'] = True
                    else:
                        output[i+1] = input[i+1]
                        output['sum'] += input[i+1]
                        if output.get(i) is not None:
                            output['skip'] = True
                else:
                    output[i] = input[i]
                    output['sum'] += input[i]

    if main_output[0]['sum'] >= main_output[1]['sum']:
        return main_output[0]['sum']
    else:
        return main_output[1]['sum']


print(get_max_sum(8, [3, 2, 3, 2, 3, 5, 1, 3]))
print(get_max_sum(5, [10, 3, 5, 7, 3]))
print(get_max_sum(5, [10, 1, 5, 7, 3]))
print(get_max_sum(5, [1, 2, 3, 4, 5]))

And I got the output correct which is this:

17
23
22

Now the thing is, I am looking for a better version of this. I know this is not the most efficient code and I will appreciate any suggestions to improve this code.

This is Code Visualization Link.

EDIT: I have made some minor changes/improvements in my code.

Answer 1

I don't fully understand your code, but it seems to look only at the presence or absence of the previous element when deciding whether to include the current one, so I constructed a test case and verified that it fails:

print(get_max_sum(6, [10, 10, 0, 0, 10, 10]))

should give 40 but actually gives 30.

---

    if main_output[0]['sum'] >= main_output[1]['sum']:
        return main_output[0]['sum']
    else:
        return main_output[1]['sum']

doesn't need to be so verbose. Prefer

   return max(main_output[0]['sum'], main_output[1]['sum'])

---

    output_1 = {'skip': True, 'sum': input[0]+input[1], 0: input[0], 1:input[1]}
    output_2 = {'skip': False, 'sum': input[0]+input[2], 0: input[0], 2:input[2]}

What you need to keep track of is the current run length, which can be from 0 (previous element not included) to 2 (both previous elements included, so must skip this one). The requirement to include the first element means that a special case is required at the start. So we get

    best_by_run_length = [float('-inf'), input[0], float('-inf')]
    for elt in input[1:]:
        best_by_run_length = [
            # Run length 0: don't include elt, preceding run length is unconstrained
            max(best_by_run_length),
            # Run length 1: include elt, preceded by run length of 0
            elt + best_by_run_length[0],
            # Run length 2: include elt, preceded by run length of 1
            elt + best_by_run_length[1]
        ]
    return max(best_by_run_length)

---

print(get_max_sum(8, [3, 2, 3, 2, 3, 5, 1, 3]))
print(get_max_sum(5, [10, 3, 5, 7, 3]))
print(get_max_sum(5, [10, 1, 5, 7, 3]))
print(get_max_sum(5, [1, 2, 3, 4, 5]))

How do you know that the output is correct? Rather than print the result, it's much more useful to print the comparison of the result against the expected value. Or you could take the testing up a level by using doctest (Python 2, Python 3).

Answer 2

I don't use Python on a day-to-day basis, so here's a basic improvement (less incredible since you edited your code but still useful). It's pretty straightforward, I just grouped your conditions differently to have less redundances.

def get_max_sum(num, input):
    output_1 = {'skip': True, 'sum': input[0]+input[1], 0: input[0], 1:input[1]}
    output_2 = {'skip': False, 'sum': input[0]+input[2], 0: input[0], 2:input[2]}

    main_output = [output_1, output_2]

    for i in range(2, num):
        for output in main_output:
            if output.get(i) is not None: #let you save on indentation
                continue
            if output['skip']:
                output['skip'] = False
                continue
            if len(input) > i+1 and input[i] <= input[i+1]: #the special case
                output[i+1] = input[i+1]
                output['sum'] += input[i+1]
                if output.get(i) is not None:
                    output['skip'] = True
            else: #all the others
                output[i] = input[i]
                output['sum'] += input[i]
                if output.get(i-1) is not None:
                    output['skip'] = True


    if main_output[0]['sum'] >= main_output[1]['sum']:
        return main_output[0]['sum']
    else:
        return main_output[1]['sum']


print(get_max_sum(8, [3, 2, 3, 2, 3, 5, 1, 3]))
print(get_max_sum(5, [10, 3, 5, 7, 3]))
print(get_max_sum(5, [10, 1, 5, 7, 3]))

As someone pointed in the comment, I'm not sure your code would work on every cases, but I'm here to improve the code, not the solution ^^

Still, consider things like [1, 8, 10, 4, 1] for example.