Talk:Maximum subarray problem: Difference between revisions

Revision as of 03:47, 20 September 2018

Revision as of 19:33, 26 February 2019

Line 96:

"(actually theta(n) is a better answer because both the lower bound and the upper bound has the same runtime. By saying the runtime is , you do not clarify that Kadane's algorithm has the same lower and upper bound, thus it is not completely correct for the run time to be )"

== the solution for taking track of the indices is wrong ==

<code>

max_ending_here = A[0]

startOld = start = end = max_so_far = 0

for i, x in (zip (range (1, len (A)), A[1:])):

if max_ending_here + x > x:

max_ending_here = max_ending_here + x

else:

max_ending_here = x;

start = i

if max_so_far < max_ending_here:

max_so_far = max_ending_here;

end = i

print (max_so_far , start, end)

</code>