Buy once and sell once for maximum profit

Question

Suppose we have stock price history, and we are allowed to buy only once and sell only once. The problem is to find the maximum profit we can make. Here is my code that I tested for basic test cases. I'm wondering if there are possible improvements for logic correctness.

My major idea is to keep record of in history minimal price, and determine if sell today (with the purchase of historical minimal price), whether we can make a larger profit.

prices = [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
result = 0
minSofar = prices[0]
for i in range(1, len(prices)):
    minSofar = min(minSofar, prices[i])
    result = max (result, prices[i] - minSofar)

print result

Answer 1

The idiom for i in range(len(var)): var[i] is frowned apon in Python, as it makes the code harder to read. If however you use for price in prices: then your code would be simpler. And the only reason you didn't do this is as you need to exclude the first price. So if you use an iterator you can do this:

prices = [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
prices = iter(prices)

result = 0
minSofar = next(prices)
for price in prices:
    minSofar = min(minSofar, price)
    result = max (result, price - minSofar)

print result

This honestly looks kida ugly, and so I'd make a function to not find the maximum, but to give us the profit for each index. So the result would look like [0, 13, 10, 0, 20, 17, 1, 0, 18, 38, 31, 43, 38, 16, 31, 27, 34]. To create this is actually really easy. make a function, and then yield rather than overwrite result. Combined with the above got me:

def profits(prices):
    prices = iter(prices)
    least = next(prices)
    yield 0
    for price in prices:
        least = min(least, price)
        yield price - least

And then to get the largest profit, you simply use max on it:

prices = [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
print max(profits(prices))

Answer 2

profit would be a better name than result.

This could be simplified to a one-liner using itertools.combinations()

profit = max(sell - buy for buy, sell in itertools.combinations(prices, 2))

Answer 3

The general idea of going through each price and modifying minSofar and result is definitely the best way. I did come up with another way:

print reduce(lambda (r,m), p: [(max(r, p - m), m) for m in (min(m,p),)][0], prices[1:], (0, prices[0]))

but, of course, that is just awful. I did it merely to entertain myself. Yours is truly the best way.

---

Enough with the silliness. A for loop has no requirement for its object except that it be iterable. You can even iterate through strings:

for char in "hello":
    print char

h
e
l
l
o

Therefore, just iterate through prices directly instead of iterating through its indexes. I would suggest using prices[1:] to prevent iterating through the entire list, but 200_success was quite right (in the comments) that it is unnecessarily expensive. Checking one extra number is cheaper than making a slice of all but one of the prices.

---

There are haters, but I believe one should generally follow PEP 8, the official style guide for Python. Of course, even the pep itself gives some examples where it should not be complied with, but I like to follow it as a general rule because it tends to make the code more readable, and when the convention is followed, it is easier for others who follow it to understand your code. According to that document, your naming does not comply with its rules guidelines on Method Names and Instance Variables:

Use the function naming rules: lowercase with words separated by underscores as necessary to improve readability.

(There's more, but it isn't relevant.)

Even if you do decide to stick with capitalized names, at least be consistent. Why is So capitalized when Far isn't? The capitalized letter makes it look like you are doing mixedCase, but you then don't capitalize Far, so it looks like the words are min and sofar. I've never heard of sofar, so I assumed that it was a foreign word until I realized what it was for.

Answer 4

The documentation for itertools.accumulate notes that you can pass min as the second argument to get a running minimum. So the maximum profit can be computed like this:

profit = max(p - m for p, m in zip(prices, accumulate(prices, min)))