Best Time To Buy And Sell Stock

                                            
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0;
        int minPrice = INT_MAX;
        
        for(int i = 0; i < prices.size(); i++) {
            minPrice = min(minPrice, prices[i]);
            maxProfit = max(maxProfit, prices[i] - minPrice);
        }
        
        return maxProfit;
    }
};

                                            
class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
        
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        
        return maxProfit;
    }
}

                                            
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        
        min_price = prices[0]
        max_profit = 0
        
        for price in prices:
            if price < min_price:
                min_price = price
            else:
                max_profit = max(max_profit, price - min_price)
        
        return max_profit

                                            
int maxProfit(int* prices, int pricesSize) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    
    for (int i = 0; i < pricesSize; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }
    
    return maxProfit;
}

                                            
public class Solution {
    public int MaxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = Int32.MaxValue;
        
        for (int i = 0; i < prices.Length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        
        return maxProfit;
    }
}

                                            
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxProfit = 0;
    let minPrice = prices[0];
    
    for (let i = 1; i < prices.length; i++) {
        minPrice = Math.min(minPrice, prices[i]);
        maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    }
    
    return maxProfit;
};

                                            
function maxProfit(prices: number[]): number {
    let maxProfit = 0;
    let minPrice = prices[0];

    for (let i = 1; i < prices.length; i++) {
        const currentPrice = prices[i];
        if (currentPrice < minPrice) {
            minPrice = currentPrice;
        } else {
            maxProfit = Math.max(maxProfit, currentPrice - minPrice);
        }
    }

    return maxProfit;
};

                                            
class Solution {
    /**
     * @param Integer[] $prices
     */
    function maxProfit($prices) {
        $maxProfit = 0;
        $minPrice = PHP_INT_MAX;
        
        foreach ($prices as $price) {
            $minPrice = min($minPrice, $price);
            $maxProfit = max($maxProfit, $price - $minPrice);
        }
        
        return $maxProfit;
    }
}

                                            
class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var maxProfit = 0
        var minPrice = Int.max
        
        for price in prices {
            minPrice = min(minPrice, price)
            maxProfit = max(maxProfit, price - minPrice)
        }
        
        return maxProfit
    }
}

                                            
class Solution {
    fun maxProfit(prices: IntArray): Int {
        var maxProfit = 0
        var minPrice = Int.MAX_VALUE
        
        for (price in prices) {
            if (price < minPrice) {
                minPrice = price
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice
            }
        }
        
        return maxProfit
    }
}

                                            
class Solution {
  int maxProfit(List<int> prices) {
    if (prices.isEmpty) {
      return 0;
    }
    
    int maxProfit = 0;
    int minPrice = prices[0];
    
    for (int i = 1; i < prices.length; i++) {
      if (prices[i] < minPrice) {
        minPrice = prices[i];
      } else if (prices[i] - minPrice > maxProfit) {
        maxProfit = prices[i] - minPrice;
      }
    }
    
    return maxProfit;
  }
}

                                            
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    
    maxProfit := 0
    minPrice := prices[0]
    
    for i := 1; i < len(prices); i++ {
        if prices[i] < minPrice {
            minPrice = prices[i]
        } else if prices[i] - minPrice > maxProfit {
            maxProfit = prices[i] - minPrice
        }
    }
    
    return maxProfit
}

                                            
# @param {Integer[]} prices
# @return {Integer}
def max_profit(prices)
    max_profit = 0
    min_price = prices[0]
    
    prices.each do |price|
        min_price = [min_price, price].min
        max_profit = [max_profit, price - min_price].max
    end
    
    max_profit
end

                                            
object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        var maxProfit = 0
        var minPrice = Int.MaxValue
        
        for (price <- prices) {
            if (price < minPrice) {
                minPrice = price
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice
            }
        }
        
        maxProfit
    }
}

                                            
impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        let mut min_price = i32::MAX;
        let mut max_profit = 0;
        
        for price in prices {
            if price < min_price {
                min_price = price;
            } else if price - min_price > max_profit {
                max_profit = price - min_price;
            }
        }
        
        max_profit
    }
}

                                            
-spec max_profit(Prices :: [integer()]) -> integer().
max_profit(Prices) ->
    MaxProfit = lists:foldl(fun(X, {MinPrice, MaxProfit}) ->
        NewMinPrice = min(X, MinPrice),
        NewMaxProfit = max(X - MinPrice, MaxProfit),
        {NewMinPrice, NewMaxProfit}
    end, {hd(Prices), 0}, tl(Prices)),
    element(2, MaxProfit).

                                            
defmodule Solution do
  @spec max_profit(prices :: [integer]) :: integer
  def max_profit(prices) do
    Enum.reduce([hd(prices) | tl(prices)], {0, hd(prices)}, fn price, {max_profit, min_price} ->
      {running_max, running_min} = if price < min_price, do: {0, price}, else: {price - min_price, min_price}
      {max(max_profit, running_max), min(running_min, min_price)}
    end) |> elem(0)
  end
end

To solve this coding challenge, we need to determine the maximum profit that can be made by buying and subsequently selling a stock on different days. The key constraint here is that we must buy the stock on a day before we sell it.

Explanation

Given an array of prices where

prices[i]

denotes the stock price on the ith day, we need to identify the best possible day to buy and the best possible future day to sell to maximize profit. We will employ a strategy that keeps track of the minimum price we've encountered so far as we iterate through the list, updating this minimum price along the way. Simultaneously, we'll keep a record of the maximum profit achievable by comparing the profit from the current day and the stored maximum profit. Here’s the step-by-step methodology to solve this problem:

Initialization:

Start by checking if the prices array is empty. If it is, return 0 as there is no way to make a profit.
Initialize
min_price

with the first day's price.
Initialize
max_profit

to 0, as no transactions have been done yet.

Iterate Through Prices:

For each price in the array, check if it is lower than the current
min_price

. If so, update
min_price

.
Calculate the potential profit by subtracting
min_price

from the current price.
Compare this potential profit to the current
max_profit

and update
max_profit

if the new profit is higher.

Return the Results:

After iterating through all prices, return
max_profit

which holds the maximum profit achievable.

Pseudocode with Comments

                                            
// Define the function to calculate the maximum profit
function maxProfit(prices):

// Check if the prices array is empty, return 0 since no transactions are possible
if prices is empty:
return 0

// Initialize minimum price to the first element in prices
min_price = prices[0]

// Initialize maximum profit to 0 since no transactions have occurred yet
max_profit = 0

// Iterate through each price in the list
for each price in prices:

// If the current price is less than the minimum price seen so far
if price < min_price:
// Update the minimum price to the current price
min_price = price
else:
// Calculate potential profit by selling at the current price
potential_profit = price - min_price

// Update the maximum profit if the potential profit is higher
if potential_profit > max_profit:
max_profit = potential_profit

// Return the maximum profit found
return max_profit

Detailed Steps in Pseudocode:

Check if the
prices

array is empty. This is crucial because an empty array signifies no stock prices available to analyze, leading to a direct return of 0, indicating no possible profit.
Initialize
min_price

to the first price in the array. This sets our baseline for the lowest price seen so far as we begin with the first day's price.
Initialize
max_profit

to 0, depicting no profit has been made yet. This will be the variable storing the highest profit as we iterate through the prices.
Begin a loop through each
price

in the
prices

array:

Inside the loop, if the current
price

is less than
min_price

, update
min_price

to this new lower price. This ensures we are always buying at the lowest price observed up to the current point.
Calculate
potential_profit

as the difference between the current
price

and
min_price

. This represents the profit if we were to sell at the current day and had bought at the lowest price seen till now.
Compare
potential_profit

to
max_profit

and update
max_profit

if the
potential_profit

is greater. This ensures that we are capturing the best possible profit scenario.

After completing the loop, return
max_profit

, which now holds the highest profit possible from the given price sequence.

Using this approach ensures a time complexity of O(n), where n is the length of the prices array, because we only pass through the list once. This efficiency is crucial given the constraints provided.