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.
Solution
This should be a lot simpler if you know how to solve 123. Best Time to But and Sell Stock III. But starting from here is better.
Since this problem is about finding a optimized (max) profit, dynamic programming should come into mind. So you maintain a minimum price as the best time to buy the stock and the time to sell it by iterating through the prices.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0, minPrice = INT_MAX;
for (auto i: prices) {
minPrice = min(minPrice, i);
profit = max(profit, i - minPrice)
}
return profit;
}
};
Below is a unnecessary version of the DP solution, followed the general solution mentioned in leetcode 123. Definitely not efficient, but its a fun thing to think about solving this in a general (other stock optimization programming problems) way.
The array holdStock optimized the best price to buy the stock (the lowest price). And the array noStock optimizes the best time to sell the stock.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<int> noStock(n+1, 0);
vector<int> holdStock(n+1, INT_MIN);
for (int i = 1; i < n+1; i++) {
holdStock[i] = max(holdStock[i-1], noStock[i] - prices[i-1]); // hold / buy stock
noStock[i] = max(noStock[i-1], holdStock[i] + prices[i-1]); // hold / sell stock
}
return noStock.back();
}
};
Related Problems
- 121 - Best Time to Buy and Sell Stock
- 122 - Best Time to Buy and Sell Stock II
- 123 - Best Time to Buy and Sell Stock III
- 188 - Best Time to Buy and Sell Stock IV
- 309 - Best Time to Buy and Sell Stock with Cooldown
- 714 - Best Time to Buy and Sell Stock with Transaction Fee