Algorithms #1

from cmath import inf
import random
from timeit import default_timer as timer
global length

length = 100


def main():
    numbers = createList(1072771)

    print("{:<30} {:<30} {:<30} {:<30} {:<30}".format('Algorithm',
          'Time Elapsed', 'Maximum Sum', 'Subarray Position', 'Time Complexity'))
    print("{:<30} {:<30} {:<30} {:<30} {:<30}".format('--------',
          '--------', '--------', '--------', '--------'))

    runAlgorithm(BruteForce(numbers))
    runAlgorithm(ImprovedApproach(numbers))
    runAlgorithm(DivideAndConquer(numbers))
    runAlgorithm(Linear(numbers))


def createList(seed):
    _ = random.seed(seed)
    return [random.randint(-100, 100) for _ in range(length)]


class Algorithm():
    def __init__(self, numbers):
        self.numbers = numbers
        self.complexity
        self.name
        self.bounds
        self.max


class BruteForce(Algorithm):
    def __init__(self, numbers):
        self.complexity = 'O(n^3)'
        self.bounds = None
        self.max = None
        self.name = 'Brute Force'
        super().__init__(numbers)

    def run(self):
        '''O(n^3) complexity, a brute force approach'''
        n = length
        m = 0
        for i in range(n):
            for j in range(i, n):
                s = 0
                for k in range(i, j + 1):
                    s += self.numbers[k]
                if m < s:
                    self.bounds = (i, j)
                    m = max(m, s)
        self.max = m
        return None


class ImprovedApproach(Algorithm):
    def __init__(self, numbers):
        self.complexity = 'O(n^2)'
        self.bounds = None
        self.max = None
        self.name = 'Improved Approach'
        super().__init__(numbers)

    def run(self):
        '''O(n^2) complexity'''
        n = length
        s = [0]*(n+1)
        for i in range(n):
            s[i+1] = s[i]+self.numbers[i]
        m = 0
        for i in range(n):
            for j in range(i, n):
                if m < s[j+1] - s[i]:
                    self.bounds = (i, j)
                m = max(m, s[j+1] - s[i])
        self.max = m
        return None


class DivideAndConquer(Algorithm):
    def __init__(self, numbers):
        self.complexity = 'O(nlogn)'
        self.max = None
        self.bounds = None
        self.name = 'Divide And Conquer'
        super().__init__(numbers)

    def run(self, lower=0, upper=length - 1):
        def maxCrossing(array, lower, mid, upper):
            sum_left = -inf
            sum_temp = 0
            cross_lower = mid
            for i in range(mid - 1, lower - 1, -1):
                sum_temp = sum_temp + array[i]
                if sum_temp > sum_left:
                    sum_left = sum_temp
                    cross_lower = i

            right = -inf
            sum_temp = 0
            cross_upper = mid + 1
            for i in range(mid, upper):
                sum_temp = sum_temp + array[i]
                if sum_temp > right:
                    right = sum_temp
                    cross_upper = i + 1
            return cross_lower, cross_upper, sum_left + right

        if lower == upper - 1:
            return lower, upper, self.numbers[lower]
        else:
            mid = (lower + upper)//2
            left_lower, left_upper, left_max = self.run(lower, mid)
            right_lower, right_upper, right_max = self.run(mid, upper)
            cross_lower, cross_upper, cross_max = maxCrossing(self.numbers, lower, mid, upper)
            if (left_max > right_max and left_max > cross_max):
                self.bounds = (left_lower, left_upper-1)
                return left_lower, left_upper, left_max
            elif (right_max > left_max and right_max > cross_max):
                self.bounds = (right_lower, right_upper-1)
                return right_lower, right_upper, right_max
            else:
                self.bounds = (cross_lower, cross_upper-1)
                return cross_lower, cross_upper, cross_max


class Linear(Algorithm):
    def __init__(self, numbers):
        self.complexity = 'O(n)'
        self.max = None
        self.bounds = None
        self.name = 'Kadane\'s Approach'
        super().__init__(numbers)

    def run(self):
        '''O(n) complexity'''
        lower = 0
        upper = 0
        m = [self.numbers[0], 0]  # m[0] is the max, m[1] is a temp dummy max
        for i in range(0, len(self.numbers)):
            upper = i
            m[1] = m[1] + self.numbers[i]
            if m[1] <= 0:
                m[1] = 0
                lower = upper + 1
            elif (m[0] < m[1]):
                m[0] = m[1]
                self.bounds = (lower, upper)

        self.max = m[0]
        return None


def runAlgorithm(algorithm):
    start = timer()
    maximum = algorithm.run()
    end = timer()
    print("{:<30} {:<30} {:<30} {:<30} {:<30}".format(algorithm.name, -start+end,
          maximum[2] if not maximum == None else algorithm.max, ', '.join(map(str, algorithm.bounds)), algorithm.complexity))


if __name__ == '__main__':
    main()