Find the best way to get the max sum in a list where sum of three consecutive elements is not allowed 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] &amp; Sum of elements : 12
  
  2 = [1, 3, 5] &amp; 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 &amp; 2, then skip 3 and choose 4 &amp; 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) &gt; i+1:
                    if input[i] &gt; 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'] &gt;= 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.
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'] &gt;= 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).