#!/usr/bin/python

import random
import time

def f1(L):
    '''Method 1: O(n^3)
    Enumerate all possible combinations of index i and j,
    calculate the cumulative sum for every pair of i and j,
    return the maximum.
    '''
    N = len(L)
    smax = sum(L)
    for i in range(N):
        for j in range(i,N):
            s = sum(L[i:j+1])
            if s > smax:
                smax = s
    return smax

def f2(L):
    '''Method 2: O(n^2)
    Calculate the cumulative sum of the first i elements csum,
    then the cumulative sum between i and j is csum[j] - csum[i],
    return the maximum.
    '''
    N = len(L)
    csum = [0]*N
    csum[0] = L[0]
    for i in range(1,N):
        csum[i] = csum[i-1] + L[i]
    smax = csum[0]
    for i in range(0,N):
      for j in range(i+1,N):
          s = csum[j] - csum[i]
          if s > smax:
              smax = s
    return smax

def f3(L):
    '''Method 3: O(n)
    Dynamic programming.
    Let S[i] be the optimal solution including L[i],
    Then the optimal solution of the original problem 
    must lie in one of S.
    i.e.at least one of L[i] must be included in the final solution
    Return max(S)
    '''
    N = len(L)
    S = [0]*N
    S[0] = L[0]
    for i in range(1,N):
        S[i] = max(S[i-1]+L[i], L[i])
    return max(S)

N = 500
LIM = 1000
# Generate a random list of N integers ranging from -LIM to LIM
L = []
for i in range(N):
    L.append(random.randint(-LIM,LIM))

# Method 1: O(n^3)
time1 = time.time()
print f1(L)
time2 = time.time()
print 'Time used by Method1:', time2-time1

# Method 2: O(n^2)
time1 = time.time()
print f2(L)
time2 = time.time()
print 'Time used by Method2:', time2-time1

# Method 3: O(n)
time1 = time.time()
print f3(L)
time2 = time.time()
print 'Time used by Method3:', time2-time1</pre>