Skip to content

Best Time to Buy and Sell Stock⚓︎

Link

Description⚓︎

You are given an array prices where prices[i] is the price of a given stock on the i-th 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 <= 10^5
  • 0 <= prices[i] <= 10^4

Solution⚓︎

Greedy Method⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = INT_MAX;
        int res = 0;
        for (int price : prices) {
            low = min(low, price);
            res = max(res, price - low);
        }
        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).

Dynamic Programming Method⚓︎

See reference (Chinese).

Way 1⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
        }
        return dp[n - 1][1];
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).

Way 2⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(2, vector<int>(2));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; i++) {
            dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]);
            dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
        }
        return dp[(n - 1) % 2][1];
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).