Skip to content
Advertisement

Python: Maximum Subarray Sum

I’ve just tried to start learning Python today, so I am not knowledgeable when it comes to it’s functions. However, I found the maximum subarray problem, and wanted to try and solve it with the few, simple logical commands I have at my disposal. I have gotten stuck, and am almost certain the problem is in my logic and not syntaxual, though I may very well be wrong. Here is my code so far…

JavaScript

The various print functions show each decision made by the program, and help me visualize what is going on as it executes the loops.

It is not giving the correct result of 105 when given the list

JavaScript

It ends up with a sum of 94, having reduced the list to

JavaScript

Sorry for the long post, but I just cannot figure out what I am doing wrong. Thank you for your help in advance!

Here is the output when the aforementioned list is given as input, I have gone through and looked at each step, and every elimination from the list seems logical to me, I do not know how one could end up with an ending sum of 105. If anyone could please help me understand, I would really appreciate it!

JavaScript

Advertisement

Answer

I’ll demonstrate what’s wrong with your algorithm with a little example.

Say the input is

JavaScript

[2] is clearly the maximum subarray. However, your algorithm will look at this part:

JavaScript

and see that it can increase the sum of the array by deleting [2, -3].

Deleting negative subarrays from the ends does the wrong thing if the maximum subarray is part of a negative subarray. You’ll need a smarter algorithm.

User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement