[CentralOH] [COhPy] DoJo Rumblings: Tonight's Python Challenge

[neil ludban]

The algorithm that I forgot to include a pointer to:

https://en.wikipedia.org/wiki/Maximum_subarray_problem

The preprocessing trick is to recognize that the difference between any two
entries in the original array is equal to the sum of the differences
between all adjacent pairs between those two entries.


On Tue, Mar 12, 2019 at 6:41 PM neil ludban <neil.ludban at gmail.com> wrote:

> #!/usr/bin/env python3.7
>
> def delta(x):
>     a = next(x)
>     for b in x:
>         yield b - a
>         a = b
>
> def positive_sums(x):
>     s = 0
>     for c in x:
>         s += c
>         if s > 0:
>             yield s
>         else:
>             s = 0
>
> prices = [ 9, 11, 8, 5, 7, 10 ]
> print(max(positive_sums(delta(iter(prices)))))
>
>
> On Thu, Mar 7, 2019 at 11:57 AM Travis Risner <deeppunster at gmail.com>
> wrote:
>
>> Here is a small problem for us to consider.  At tonight’s DoJo meeting
>> we will work together to solve this as individuals or small groups.  We
>> will also discuss the advantages of each approach.
>>
>>         Given a array of numbers representing the stock prices of a
>> company in
>>         chronological order, write a function that calculates the maximum
>> profit you
>>         could have made from buying and selling that stock once. You must
>> buy
>> before
>>         you can sell it.
>>
>>         For example, given [9, 11, 8, 5, 7, 10], you should return 5,
>> since you
>>         could buy the stock at 5 dollars and sell it at 10 dollars.
>>
>> DoJo is at Smokehouse Brewing, 1130 Dublin Road, Columbus, Ohio.  Join
>> us at 6:00 or any time after that!
>>
>> Travis
>> _______________________________________________
>> CentralOH mailing list
>> CentralOH at python.org
>> https://mail.python.org/mailman/listinfo/centraloh
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/centraloh/attachments/20190409/a2744e3f/attachment-0001.html>