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.