3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This doesn't seem to work for [1,2,3,4,5] for me (but I might not be testing it correctly) (1+2+4+5 = 12, but outputs 9). \$\endgroup\$ – my pronoun is monicareinstate Aug 9 at 13:58
  • \$\begingroup\$ @someone Thanks for replying. Yes, you are right. My bad. let me check. \$\endgroup\$ – Tony Montana Aug 9 at 14:03
  • 1
    \$\begingroup\$ The simplest approach I can think of is dynamic programming where dp[current index][number of elements chosen in a row] = highest sum possible. \$\endgroup\$ – my pronoun is monicareinstate Aug 9 at 14:39
  • \$\begingroup\$ @someone can you provide some general example based on that or psudo-code maybe? \$\endgroup\$ – Tony Montana Aug 9 at 14:53
  • 1
    \$\begingroup\$ Step by step, with practice. \$\endgroup\$ – Mast Aug 15 at 11:16
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for replying. I haven't tested your code yet. But I have tried above list example and it returns 15, which is I think, correct answer. So far so, my code is working fine. Let see whether we can improve it or not. Main concern for me is, the two dictionary which I initialized in function with some values from the input list. \$\endgroup\$ – Tony Montana Aug 9 at 15:00
  • \$\begingroup\$ @TonyMontana Shouldn't the correct answer be 19 (8+10+1) ? \$\endgroup\$ – Nomis Aug 9 at 15:44
  • \$\begingroup\$ sorry, it seems I have not cleared this confusion already. The first element of the list must be included in the total sum. \$\endgroup\$ – Tony Montana Aug 9 at 15:51
  • \$\begingroup\$ @Naomis, I have added some examples in the above question. I hope it might clear all confusions. \$\endgroup\$ – Tony Montana Aug 9 at 16:12
  • 3
    \$\begingroup\$ Since this is Code Review, please explain how your solution is better than the original code, so that we may learn from your thought process. Otherwise this is not a valid answer. \$\endgroup\$ – 200_success Aug 9 at 17:44
0
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.