Python: Write a program to find the time period(s) of the largest price drop(s)

i am suppose to solve this question but i am stuck.

Write a program to find the time period(s) of the largest price drop(s) when a list of price(s) is given. For instance, if the list is [300,301,303,299,300,298,301,305], then there is one period of the largest price drop: from time 2 with price 303 to time 5 with price 298.

Below is my solution but there is a flaw

def maxdrop(p):
  high = low = drop = newhigh = 0
  for i in range(len(p)):
    if p[i] >= p[high]:
      newhigh = i # invariant: p[high] <= p[newhigh]
    else: # s开发者_如何学编程o: p[i] < p[high] <= p[newhigh]
      newdrop = p[newhigh] - p[i]
      if newdrop >= drop:
        high, low, drop = newhigh, i, newdrop
  return ((high, p[high]), (low, p[low]), drop)
def test():
  p = [20,22,19,20,24,18,21,24,27]
  print p, maxdrop(p)
  p = list(reversed(p))
  print p, maxdrop(p)
  if __name__ == "__main__":
  test()

If you try with the below list [2,1,2,3,4,3,2]

the sharpest drop should occurs over 4,3,2 – the last 3 elements. But with my code, the output is 2,1 – the first 2 elements.

Please assist, thanks!

You want the maximum sum contiguous sequence, but inverted. This page has the best explanation of it I have seen.

The basic algorithm will look like this:

>>> def min_sum_subsequence(seq):
...     minsofar = 0
...     minendinghere = 0
...     for s in seq:
...         # invariant: maxendinghere and maxsofar are accurate
...         # are accurate up to s
...         minendinghere = min(minendinghere + s, 0)
...         minsofar = min(minsofar, minendinghere)
...     return minsofar
... 
>>> series = [300,301,303,299,300,298,301,305]
>>> returns = [series[i] - series[i-1] for i in range(1, len(series))]
>>> min_sum_subsequence(returns)
-5

You have to add code to keep track of the index of the start and finish.

Its always best to print all the values and check out the results.

The problem with your code is when you write p[i]> p[high] you update the value of newhigh but the value of high is not changing.

Just write it as p[i] > p[newhigh] and check out if its giving the correct results. I have'nt checked if it will give the correct output. Do that on your own.

Though you can always use the shortened versions mentioned above.

Here's my try at it. It works correctly on all the examples that you gave.

I basically just go through the array and when there is a drop between two points, referring to the first point as A, look ahead until there is a value that is higher than A. I keep track of the minimum in this region. If the difference between A and the minimum is a bigger drop than what I've already found, I hold onto it. I then start looking again for a drop between two points, starting at the next point that was higher than A.

Here's the code. It isn't very Python-esque, but it works pretty well (I'd just go to Cython if I needed it to be faster). Also, it returns the magnitude of the drop.

def maxdrop(p):
    bestdrop = 0
    wheredrop = -1,-1
    i = 0
    while i < len(p) - 1:
        if p[i+1] < p[i]:
            bestlocal = p[i+1]
            wherelocal = i+1
            j = i + 1
            while j < len(p) - 1 and p[j + 1] < p[i]:
                j += 1
                if p[j] < bestlocal:
                    bestlocal = p[j]
                    wherelocal = j
            if p[i] - bestlocal > bestdrop:
                bestdrop = p[i] - bestlocal
                wheredrop = i, wherelocal
            i = j+1
        else:
            i += 1
    return bestdrop,wheredrop

A big problem with your code is that you only look at the next value for the biggest drop after a new high value is found.

Having copy-pasted your code and indented it, you're nearly there. Where you test:

if p[i] >= p[high]:

You're not considering that p[i] might be >= p[high], but less than p[newhigh].

You are asking for the largest non-monotonically decreasing sequence. There is a similar question for monotonically in this question. Lots of ways to approach this problem. Here is a recursive approach.

def biggest_drop(sequence):
    seq_min, seq_max = min(sequence), max(sequence)
    imin, imax = sequence.index(seq_min), sequence.index(seq_max)
    if imin == imax:
        return None
    if imin < imax:
        # split the sequence and look for local drops
        drop_a = biggest_drop(sequence[:imax])
        drop_b = biggest_drop(sequence[imax:])
        if drop_a is None or drop_b is None:
            if drop_a:
                return drop_a
            return drop_b
        value_a = drop_a[0] - drop_a[-1] 
        value_b = drop_b[0] - drop_b[-1]
        if value_a > value_b:
            return drop_a
        else:
            return drop_b
    return sequence[imax:imin+1]

Here is my solution:

start_=stop_=None
min_=0
for start in range(len(li)-1):
    for stop in range(start+1, len(li)):
        tmp= li[stop]-li[start]
        if tmp<min_:
            min_=tmp
            start_=start
            stop_=stop
print min_
print (start_, stop_)

It works for your sample.

Python allows for much shorter code:

l = [300,301,303,299,300,298,301,305]

max([(l[i] - l[j], i, j) for i in range(len(l)) for j in range(i, len(l))], key=lambda x:x[0])

(5, 2, 5)

This can maybe be shortened, but it's a good starting point. Also, as others said, please use [homework] tag if appropriate. Edit: this answers (drop, begin, end).

There's a faster way to compute mins than this example, but this is concise and readable:

>>> data = [300, 301, 303, 299, 300, 298, 301, 305]
>>> mins = [min(data[i:]) for (i, _) in enumerate(data)]
>>> mins
[298, 298, 298, 298, 298, 298, 301, 305]
>>> drops = [ d - m for (d, m) in zip(data, mins)]
>>> drops
[2, 3, 5, 1, 2, 0, 0, 0]
>>> [ (i, data[i] - drop) for (i, drop) in enumerate(drops) if drop == max(drops) ]
[(2, 298)]

Knowing that the start of the period is 2 and the low point is 298, the end of the period is:

>>> [ i for (i, x) in enumerate(data) if i > 2 and x == 298]
[5]