min sum of consecutive values with Divide and Conquer

Question

Given an array of random integers

N = [1,...,n]

I need to find min sum of two consecutive values using divide and conquer. What is not working here but my IQ?

def minSum(array):
    if len(array) < 2:
        return array[0]+array[1]

    if (len(a)%2) != 0:
        mid = int(len(array)/2)
        leftArray = array[:mid]
        rightArray = array[mid+1:]
        return min(minSum(leftArray),minSum(rightArray),crossSum(array,mid))
    else:
        mid = int(len(array)/2)
        leftArray = array[:mid]
        rightArray = array[mid:]
        return min(minSum(leftArray), minSum(rightArray), array[mid]+array[mid+1])


def crossSum(array,mid):
    return min(array[mid-1]+array[mid],array[mid]+array[mid+1])

Answer 1

The main problem seems to be that the first condition is wrong: If len(array) < 2, then the following line is bound to raise an IndexError. Also, a is not defined. I assume that that's the name of the array in the outer scope, thus this does not raise an exception but just silently uses the wrong array. Apart from that, the function seems to more-or-less work (did not test it thoroughly, though.

However, you do not really need to check whether the array has odd or even length, you can just use the same code for both cases, making the crossSum function unneccesary. Also, it is kind of confusing that the function for returning the min sum is called maxSum. If you really want a divide-and-conquer approach, try this:

def minSum(array):
    if len(array) < 2:
        return 10**100
    elif len(array) == 2:
        return array[0]+array[1]
    else:
        # len >= 3 -> both halves guaranteed non-empty
        mid = len(array) // 2
        leftArray = array[:mid]
        rightArray = array[mid:]
        return min(minSum(leftArray),
                   minSum(rightArray),
                   leftArray[-1] + rightArray[0])

import random
lst = [random.randint(1, 10) for _ in range(20)]
r = minSum(lst)
print(lst)
print(r)

Random example output:

[1, 5, 6, 4, 1, 2, 2, 10, 7, 10, 8, 4, 9, 5, 7, 6, 5, 1, 4, 9]
3

However, a simple loop would be much better suited for the problem:

def minSum(array):
    return min(array[i-1] + array[i] for i in range(1, len(array)))