:orphan:

Best Time to Buy and Sell Stock
===============================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

You are given an array ``prices`` where ``prices[i]`` is the price of a
given stock on the ``i``\ :sup:```th``` day.

You want to maximize your profit by choosing a **single day** to buy one
stock and choosing a **different day in the future** to sell that stock.

Return *the maximum profit you can achieve from this transaction*. If
you cannot achieve any profit, return ``0``.

 

**Example 1:**

::


   Input: prices = [7,1,5,3,6,4]
   Output: 5
   Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
   Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

**Example 2:**

::


   Input: prices = [7,6,4,3,1]
   Output: 0
   Explanation: In this case, no transactions are done and the max profit = 0.

 

**Constraints:**

- ``1 <= prices.length <= 10``\ :sup:```5```
- ``0 <= prices[i] <= 10``\ :sup:```4```

.. highlight:: python

Pattern
-------
Array, Dynamic Programming

Solution
--------
Note that we only need to find the maximum possible profit, not the buy and
sell days which simplifies the problem. We make money by buying low and
selling high. Suppose we buy at price :math:`a`. Then we should sell at the
highest price before it drops below :math:`a`. If ``prices = [1, 3, 2, 4]``,
then we should ignore the temporary drop from 3 to 2 and hold until 4.

Store the price we paid for the stock as ``buy_price`` and the maximum profit
so far as ``max_profit``. We initialize ``max_profit = 0`` and can update each
day. ::

    max_profit = max(price - buy_price, max_profit)

We update ``buy_price`` only when we find a lower price.

Code
----

.. literalinclude:: ../problems/easy/best-time-to-buy-and-sell-stock/best_time_to_buy_and_sell_stock__approach_1.py
    :language: python
    :lines: 10-

Test
----
>>> from best_time_to_buy_and_sell_stock__approach_1 import maxProfit
>>> maxProfit([7, 1, 5, 3, 6, 4])
5
>>> maxProfit([7, 6, 4, 3, 1])
0

Complexity
----------
| :math:`n` is the length of the input array.
| Time: :math:`O(n)` — single pass through the array
| Auxiliary Space: :math:`O(1)` — only 2 variables to store the buy price and max profit

.. autofunction:: best_time_to_buy_and_sell_stock__approach_1.maxProfit