Maximum sum subarray returning wrong output

Question

Algorithm looks correct, not able to figure out where the mistake is. Code returns from 8 to 10 is max subarray with total of 32. But actual answer is 8 to 11 with total of 43.

import sys
import math

def maxtuple(lss,rss):
  if lss[2] > rss[2]:
      return lss
  else:
      return rss

def crosssubarray(A, start, mid, end):
  ls=rs=-sys.maxsize
  maxleft=0
  maxright=0
  sum = 0;
  for i in reversed(range(start, mid)):
    sum = sum + A[i]
    print(i)
    if sum > ls:
        ls = sum
        maxleft = i
  sum = 0
  for i in range(mid+1, end):
    sum = sum+ A[i]
    if sum > rs:
        rs = sum
        maxright = i
  return (maxleft, maxright, ls+rs)

def maxsubarray(A,start,end):
  if start == end:
    return (start,end,A[start])
  else:
    mid = (start+end)/2
    lss = maxsubarray(A, start, mid)
    rss = maxsubarray(A, mid+1, end)
    css = crosssubarray(A, start, mid, end)
    maxsub = maxtuple(lss,rss)
    maxall = maxtuple(maxsub, css)
    return maxall`enter code here`

A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
print(maxsubarray(A,0,15))

sorry, the acutal output should be 7 to 10 with total 43

Sivabushan
– Sivabushan

2017-06-05 06:29:31 +00:00
Commented Jun 5, 2017 at 6:29 — Sivabushan
– Sivabushan, Commented Jun 5, 2017 at 6:29

Peter de Rivaz · Accepted Answer · 2017-06-05 06:35:54Z

1

The problem is that range(start, mid) produces start,start+1,..,mid-1 but does not include mid.

This means that your crosssubarray does not include the middle value.

Instead try:

for i in reversed(range(start, mid+1)):

answered Jun 5, 2017 at 6:35

Peter de Rivaz

33.6k4 gold badges51 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Maximum sum subarray returning wrong output

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related