#!/usr/bin/python3
"""Leetcode problem: maximum profit available for a given price series.

Given the prices on N successive days, choose the best days to buy one
share and then sell it again (later!), and return the profit, or 0 if
there is no possible profit.

That is, what is max(∀i: ∀j > i: aⱼ - aᵢ)?  Or 0 if that's negative.

It took me a long time to figure out the simple solution, so I
probably would have failed this as an interview question, though I did
get to a linear-time solution pretty quickly.  My steps were:

- Simple nested loop, written as a genex.

- Hmm, can I precompute a data structure to shortcut the inner loop?
  Yes, an array will work, because the inner loop just computes the
  maximum of some suffix of the input array (i.e. max(a[j:len(a)]),
  and we can compute all of those in one backward pass.  It took me a
  while to get the array indexing right because it *was* a backward
  pass.

- Building this array backwards is awkward; can we build it forward
  instead?  Well, there's a symmetry in the problem between the
  minimums of prefixes (optimal buy prices) and the maximums of
  suffixes (optimal sell prices), and we could build an array of
  minimums-of-prefixes left to right, then iterate over the possible
  sell prices while indexing into the array of buy prices we computed
  in the first pass.

- Hmm, actually now we can do both of those "passes" at once, because
  we only care about the buy prices to the left of a candidate sell
  price.

- Oh actually we don't even need the array because we only ever use
  the last item we added to it.  All we need for that is a regular int
  variable.  That's a much better solution because it's not just
  linear time, it's constant space!

The final version is only about four or five reasonably clear lines of
code which are obvious in retrospect, no bigger than my original
quadratic-time solution, which makes me a little embarrassed that it
took me so long to figure it out.

"""
try:
    from typing import List, Any
except ImportError:
    pass


prices = [7, 1, 5, 3, 6, 4]     # example data


def maxProfit(prices: List[int]) -> int:
    ## Simply restate the problem in Python without optimization. ##
    # Generator expressions and max() allow us to do this very
    # concisely.
    return (0 if len(prices) < 2
            else max(0, max(prices[j] - p
                            for i, p in enumerate(prices)
                            for j in range(i+1, len(prices)))))


def maxProfit_imperative(prices: List[int]) -> int:
    ## Same thing, but longer because it doesn't use genexes. ##
    highest = 0
    for i, p in enumerate(prices):
        for j in range(i+1, len(prices)):
            profit = prices[j] - p
            if profit > highest:
                highest = profit

    return highest


def maxProfit_linear(prices: List[int]) -> int:
    ## Linear-time solution. ##
    if not prices:
        return 0

    ## Precompute best sale prices after day j. ##

    sale: List[Any] = [None] * len(prices)

    # prefix sum over reversed array with respect to max
    highest = prices[-1]
    for i in range(len(prices)):  # 0, 1, 2, 3, 4, 5
        j = len(prices) - i - 1   # 5, 4, 3, 2, 1, 0
        if prices[j] > highest:
            highest = prices[j]  # highest = max(highest, prices[j])

        # Now, highest == max(prices[j:]).
        sale[j] = highest

    ## Compute best profit. ##

    highest = 0

    for i, p in enumerate(prices):
        if sale[i] - p > highest:
            highest = sale[i] - p

    return highest


def maxProfit_simple(prices: List[int]) -> int:
    ## After thinking about the problem more I saw it was much
    ## simpler.  I've annotated the code with comments showing the
    ## values assigned on successive loop iterations when called with
    ## the example data.
    if not prices:
        return 0

    best = 0
    buy = prices[0]          # 7

    for sell in prices:      # 7,  1,  5,  3,  6,  4
                       # buy:  7,  7,  1,  1,  1,  1
        profit = sell - buy  # 0, -6,  4,  2,  5,  3
        if profit > best:
            best = profit    # 0,      4,      5

        if sell < buy:
            buy = sell       #     1

    return best


def maxProfit_short(prices: List[int]) -> int:
    ## Or you can write it this way if you're in a hurry or you think
    ## it's more readable, but the code is one fourth as fast.
    best, buy = 0, prices[0] if prices else 0

    for sell in prices:
        best, buy = max(best, sell - buy), min(buy, sell)

    return best


if __name__ == '__main__':
    print(maxProfit(prices))