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…

def maxSequence(arr): #Latest attempt, some issue.
  old_arr = []
  print(arr)
  while old_arr != arr:
    old_arr = arr
    if arr[0] > 0 and arr[len(arr)-1] > 0: #For when both sides are positive, need to be sure there is not anything to be gained by eliminating some side section
      new_sum = 0
      y=0
      while new_sum >= 0 and y != -1:
        new_sum = sum(arr[:y])
        y=y+1
        if y == len(arr)-1:
          y=-1
      if y != -1:
        arr = arr[y-1:]
      print("left %s" %(new_sum))
      print("left %s" % (arr))
      new_sum = 0
      y = 0
      while new_sum >= 0 and y != -1:
        new_sum=sum(arr[(len(arr)-y):])
        y=y+1
        if y == len(arr)-1:
          y=-1
      if y != -1:
        arr = arr[:len(arr)-y+1]
      print("right %s" %(new_sum))
      print("right %s" % (arr))
    else:
      while arr[0] < 0 or arr[len(arr)-1] < 0: #To eliminate negatives on sides
        if arr[0] < 0:
         arr = arr[1:]
        if arr[len(arr)-1] < 0:
         arr = arr[:len(arr)-1]
        print("negative %s" % (arr))
  print(arr)
  print(sum(arr))

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

[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]

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

[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]

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!

[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, 
-27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, 
-25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]
negative [26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, 
-8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 
11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
left -22
left [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, 
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
right -8
right [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, 
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25, -22, 8, 9, -4]
negative [3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, 
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25, -22, 8, 9]
left -3
left [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, 
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, 
-13, -13, 25, -22, 8, 9]
right -5
right [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, 
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, 
-13, -13, 25]
negative [15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, 
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, 
-13, -13, 25]
left -5
left [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25]
right -1
right [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6]
negative [1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 
6]
left -13
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6]
right -12
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
left 84
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
right -8
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
left 77
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
right 53
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
94

Answer

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

Say the input is

[2, -3, 1]

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

[2, -3, 1]
 ^^^^^

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.

Advertisement

Answer