Leetcode 121. Best Time to Buy and Sell Stock
Problem Explanation
You are given an array representing the price of a stock on a given day (array index). You are also allowed to make one transaction only (you can buy and then sell the stock once). Your task is to calculate the maximum profit you can get.
The approach in the code above finds the maximum possible profit by comparing the current profit (sellOne) with the maximum profit that can be made by selling the stock on the current day (holdOne + price), and updates sellOne. It then updates holdOne with the maximum of itself and the negative of the current price. This way, holdOne always contains the maximum possible profit that can be made from a transaction ending on a given day.
For example, given the array [7,1,5,3,6,4]
,
- On day 1, the maximum profit is 0 (since you can't sell the stock before you buy it).
- On day 2, you can buy the stock at the price 1.
- On day 3, the maximum profit that can be made by selling the stock is 5-1 = 4.
- On day 4, the maximum profit that can be made by selling the stock is 5-1 = 4.
- On day 5, the maximum profit that can be made by selling the stock is 6-1 = 5.
- On day 6, the maximum profit that can be made by selling the stock is still 5 (since selling the stock on this day would lead to a profit of 4 only).
So, the maximum possible profit is 5.
Python Solution
1 2python 3class Solution: 4 def maxProfit(self, prices): 5 sellOne, holdOne = 0, float('-inf') 6 7 for price in prices: 8 sellOne = max(sellOne, holdOne + price) 9 holdOne = max(holdOne, -price) 10 11 return sellOne
Java Solution
1
2java
3public class Solution {
4 public int maxProfit(int[] prices) {
5 int sellOne = 0, holdOne = Integer.MIN_VALUE;
6
7 for (int price : prices) {
8 sellOne = Math.max(sellOne, holdOne + price);
9 holdOne = Math.max(holdOne, -price);
10 }
11
12 return sellOne;
13 }
14}
Javascript Solution
1 2javascript 3class Solution { 4 maxProfit(prices) { 5 let sellOne = 0, holdOne = -Infinity; 6 7 for (let price of prices) { 8 sellOne = Math.max(sellOne, holdOne + price); 9 holdOne = Math.max(holdOne, -price); 10 } 11 12 return sellOne; 13 } 14}
C++ Solution
1 2cpp 3class Solution { 4public: 5 int maxProfit(vector<int>& prices) { 6 int sellOne = 0; 7 int holdOne = INT_MIN; 8 9 for (int price : prices) { 10 sellOne = max(sellOne, holdOne + price); 11 holdOne = max(holdOne, -price); 12 } 13 14 return sellOne; 15 } 16};
C# Solution
1
2csharp
3public class Solution {
4 public int MaxProfit(int[] prices) {
5 int sellOne = 0, holdOne = Int32.MinValue;
6
7 foreach (int price in prices) {
8 sellOne = Math.Max(sellOne, holdOne + price);
9 holdOne = Math.Max(holdOne, -price);
10 }
11
12 return sellOne;
13 }
14}
In all these solutions, we initialize sellOne
to 0 and holdOne
to negative infinity (or the smallest possible Integer, if the language doesn't support infinity), and then for each price in the array, we update sellOne
and holdOne
accordingly. The final result is the value of sellOne
, which is the maximum profit that can be made.## Ruby Solution
1 2ruby 3class Solution 4 def maxProfit(prices) 5 sellOne = 0 6 holdOne = -1.0/0.0 # negative infinity in Ruby 7 8 prices.each do |price| 9 sellOne = [sellOne, holdOne + price].max 10 holdOne = [holdOne, -price].max 11 end 12 13 sellOne 14 end 15end
PHP Solution
1
2php
3class Solution {
4 function maxProfit($prices) {
5 $sellOne = 0;
6 $holdOne = -PHP_INT_MAX; // negative infinity in PHP
7
8 foreach ($prices as $price) {
9 $sellOne = max($sellOne, $holdOne + $price);
10 $holdOne = max($holdOne, -$price);
11 }
12
13 return $sellOne;
14 }
15}
Swift Solution
1 2swift 3class Solution { 4 func maxProfit(prices: [Int]) -> Int { 5 var sellOne = 0 6 var holdOne = -Int.max // negative infinity in Swift 7 8 for price in prices { 9 sellOne = max(sellOne, holdOne + price); 10 holdOne = max(holdOne, -price); 11 } 12 13 return sellOne 14 } 15}
Conclusion
As we can see, the approach to solve this problem is quite consistent across different programming languages. The main idea is to keep track of the maximum profit at each point in time and return the highest profit in the end. It is important to notice that we are using the concept of dynamic programming here: instead of calculating the maximum profit for each day from scratch, we are using the previous computed values to make the calculation more efficient. This concept is crucial for solving many algorithmic problems and is important to master.
Finally, it should also be noted that this problem assumes that the prices array is not empty and that it contains at least two prices (i.e., the stock is bought and sold on different days). This assumption simplifies the problem, but in a real-world scenario, you would need to handle cases where the prices array is empty or contains only one price.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.