'''
  author:
  date:
  description: Slow and fast algorithms for this problem'''

import numpy as np

def slow_approach(x):
  ''' A bad solution for finding the worst sequence of days.
  Runs in O(N^3) time.'''

  def compute_profit(a,b):
    '''Compute the profit starting on day 'a' and ending on day 'b',
    day b included.'''
    return sum(x[a:(b+1)])

  worst_profit = compute_profit(0,0) # Initialize it to anything reasonable.
  worst_profit_indices = (0,0)
  for i in xrange(0, N):
    for j in xrange(i, N):
      current_profit = compute_profit(i,j)
      if (current_profit < worst_profit):
        worst_profit = current_profit
        worst_profit_indices=(i,j)

  return (worst_profit, worst_profit_indices)

def fast_approach(x):
  '''Use dynamic programming. The basic idea
  is that, rather than solving the problem directly,
  find the worst sequence of days *beginning* on day 'i'
  for the i different possibilities of i.
  We can compute this easily for i=N, then use that
  solution to compute for i=N-1, etc.
  '''
  sol_list = [0 for i in range(N)]

  # end_list[i] is the end point of the interval starting at i
  end_list = [0 for i in range(N)]

  # Only one possible choice for i=N
  sol_list[N-1] = x[N-1]
  end_list[N-1] = N-1

  idx_list = range(N-1)
  idx_list.reverse()

  for i in idx_list:
    v1 =  sol_list[i+1]+x[i]
    v2 = x[i]
    if (v1 > v2):
      '''Then best off making the list just (i)'''
      sol_list[i] = v2
      end_list[i] = i
    else:
      ''' Then we can extend the solution starting at i+1
      with the index i'''
      sol_list[i] = v1
      end_list[i] = end_list[i+1]

  min_v = min(sol_list)
  idx_min = sol_list.index(min_v)
  return (min_v, (idx_min,end_list[idx_min]))

# List of N different numbers
N=3
trials=100

for i in range(trials):
  x = np.random.randn(N)
  result_slow = slow_approach(x)
  result_fast = fast_approach(x)
  print "Our worst profit using fast alg is: " + repr(result_fast)
  print "Our worst profit using slow alg is: " + repr(result_slow)
  if (result_slow[1] != result_fast[1]):
    print "Fails on example: " + repr(x)
    break