LeetCode 121. Best Time to Buy and Sell Stock

Question

You are given an array prices where prices[i] is the price of a given stock on the ith 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 <= 105
• 0 <= prices[i] <= 104

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

Solution

The best time to buy and sell can be interpreted as two forms:

1. the lowest price we have ever seen to buy + current price to sell
2. current price to buy + the highest price in the future to sell

To solve these problems of a flexible window, one key point is to get a reliable value of one end first and traverse the other end.

In the following implementation, we choose the first form so we traverse the array from the left to the right.

public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }
    int maxProfit = 0;
    // min price that has been seen
    int minPrice = Integer.MAX_VALUE;
    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        // the max profit if selling the stock on the ith day
        maxProfit = Math.max(maxProfit, price - minPrice);
    }
    return maxProfit;
}