Skip to content

121. Best Time to Buy and Sell Stock

Description

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

Solutions

Solution 1: Enumerate + Maintain the Minimum Value of the Prefix

Thinking

One buy and one sell; trying every pair is \(O(n^2)\) and \(n\) can reach \(10^5\). For a fixed sell day the best buy is the minimum price before it. Scan while keeping the prefix minimum, update the answer by today's price minus that minimum, then fold today into the prefix.

We can enumerate each element of the array \(nums\) as the selling price. Then we need to find a minimum value in front of it as the purchase price to maximize the profit.

Therefore, we use a variable \(mi\) to maintain the prefix minimum value of the array \(nums\). Then we traverse the array \(nums\) and for each element \(v\), calculate the difference between it and the minimum value \(mi\) in front of it, and update the answer to the maximum of the difference. Then update \(mi = min(mi, v)\). Continue to traverse the array \(nums\) until the traversal ends.

Finally, return the answer.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(nums\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans, mi = 0, inf
        for v in prices:
            ans = max(ans, v - mi)
            mi = min(mi, v)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0, mi = prices[0];
        for (int v : prices) {
            ans = Math.max(ans, v - mi);
            mi = Math.min(mi, v);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0, mi = prices[0];
        for (int& v : prices) {
            ans = max(ans, v - mi);
            mi = min(mi, v);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func maxProfit(prices []int) (ans int) {
    mi := prices[0]
    for _, v := range prices {
        ans = max(ans, v-mi)
        mi = min(mi, v)
    }
    return
}

1
2
3
4
5
6
7
8
9
function maxProfit(prices: number[]): number {
    let ans = 0;
    let mi = prices[0];
    for (const v of prices) {
        ans = Math.max(ans, v - mi);
        mi = Math.min(mi, v);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut mi = prices[0];
        for &v in &prices {
            ans = ans.max(v - mi);
            mi = mi.min(v);
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let ans = 0;
    let mi = prices[0];
    for (const v of prices) {
        ans = Math.max(ans, v - mi);
        mi = Math.min(mi, v);
    }
    return ans;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public class Solution {
    public int MaxProfit(int[] prices) {
        int ans = 0, mi = prices[0];
        foreach (int v in prices) {
            ans = Math.Max(ans, v - mi);
            mi = Math.Min(mi, v);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $ans = 0;
        $mi = $prices[0];
        foreach ($prices as $v) {
            $ans = max($ans, $v - $mi);
            $mi = min($mi, $v);
        }
        return $ans;
    }
}

Comments