# Problem Description

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

# Analysis

## Idea 1

When I saw this problem, my first thought was to go through all of the prices and find the min and max in O(n) time and compute the maximum profit with (max - min).

However, this idea is wrong. Let’s see the following graph.

The min and max of this sotck price graph is min2 and max1. But (max1 - min2) is not what we want since we can’t sell a stock before buy it(max1 is before min2).

## Idea 2

Then I try to solve it using Dynamic Programming.

Let OPT(i, k) denotes the maximum we get at day k if we buy the stock at day i.

Let $P_i$ denotes the price of stock at day i.

Let optTal denotes the maximum we get.

Then we have:

$ OPT(i, k) = \begin{cases} OPT(i, k - 1) & \text{not sell at day k} \\ P_k - P_i & \text{sell at day k} \end{cases} $and the optimal:

$ \begin{align} optTotal = max\{OPT(i, j)\} \\ 1 \le i \le n \\ i \le j \le n \end{align} $With this formula, we can calculate the correct answer in $O(n^2)$ time.

However, this solution is not efficient and will exceed the time limit of LeetcodeOJ.

## Idea 3

We can go through all of the prices and update the min. Compute the profit we can get at day i by calculate ($P_i$ - min), update the max if we get a higher profit.

The complexity is O(n).

This solution works great!

# Solution

## Dynamic Programming Version 1(not good)

1 | /** |

## Dynamic Programming Version 2 (good)

1 | /** |