[LeetCode 121] Best Time to Buy and Sell Stock

Question

link

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.

Stats

Frequency	1
Difficulty	2
Adjusted Difficulty	2
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a question from a MIT course, Hacking a Google Interview.

I did not solve it, but it’s actually very simple to do.

Solution

The solution is explained here:

To solve this problem efficiently, you would need to track the minimum value’s index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).

Time is O(N)

Code

public int maxProfit(int[] prices) {
    int len = prices.length;
    if (len <= 1) return 0;
    int min = prices[0];
    int max = Integer.MIN_VALUE;
    for (int i = 1; i < len; i ++) {
        max = Math.max(max, prices[i] - min);
        min = Math.min(min, prices[i]);
    }
    return Math.max(max, 0);
}