Algorithm Puzzles: Best Time to Buy and Sell Stock

Posted on Edited on In Views: Word count in article: 140 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Best Time to Buy and Sell Stock

Puzzle

Puzzle from leetcode:
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.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
 public:
  int maxProfit(const std::vector<int>& prices) const {
    int currentMaxProfit = 0;
    int currentMinPrice = prices[0];
    const int pricesSize = prices.size();

    for (int i = 0; i < pricesSize; i++) {
      currentMinPrice = std::min(currentMinPrice, prices[i]);
      currentMaxProfit =
          std::max(currentMaxProfit, prices[i] - currentMinPrice);
    }

    return currentMaxProfit;
  }
};

T.C. should be O(n).
S.C. should be O(1)