Best Time To Buy And Sell Stock Problem


Description

LeetCode Problem 121.

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:

1
2
3
4
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:

1
2
3
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


Sample C++ Code

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




Related Posts

Best Time To Buy And Sell Stock With Cooldown Problem

LeetCode 309. You are given an array prices where prices[i]...

Maximum Product Subarray Problem

LeetCode 152. Given an integer array nums, find a contiguous...

House Robber Problem

LeetCode 198. You are a professional robber planning to rob...

Dungeon Game Problem

LeetCode 174. The demons had captured the princess and imprisoned...

Best Time To Buy And Sell Stock IV Problem

LeetCode 188. You are given an integer array prices where...

Palindrome Partitioning II Problem

LeetCode 132. Given a string s, partition s such that...