## Description

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

Say you have an array for which the *i*^{th} 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.

**Example 1:**

1 2 3 4 |
Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) |

**Example 2:**

1 2 3 4 |
Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0. |

## Explanation

The problem is seeking the max profit in buying and selling stocks.

This is a simple modeling stocks trading in real life. The essence of the problem is looking for the max value of prices[i2] – prices[i1], i2 > i1.

prices[i2] is the max value in the array. prices[i1] is the minimum value in the array.

It’s easy to solve the problem by keep tracking of the minimum price and max profit when iterating the array.

## Video Tutorial

## Java Solution

1 2 3 4 5 6 7 8 9 10 11 |
public class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; int minPrice = Integer.MAX_VALUE; for (int i = 0; i < prices.length; i++) { minPrice = Math.min(minPrice, prices[i]); maxProfit = Math.max(maxProfit, prices[i] - minPrice); } return maxProfit; } } |