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.
Examples:
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.Solution in Python:
Python
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# If there are no prices or only one price, no profit can be made
if not prices or len(prices) < 2:
return 0
# Initialize minimum price to the first price in the list
min_price = prices[0]
# Initialize max profit to zero as no transaction has been made yet
max_profit = 0
# Loop through each price starting from the second price
for price in prices[1:]:
# Calculate profit if selling at current price
profit = price - min_price
# Update max profit if current profit is greater
if profit > max_profit:
max_profit = profit
# Update min price if current price is lower
if price < min_price:
min_price = price
return max_profitExplanation
- Initial Check: If the list is empty or has only one price, no transactions can be made, so the profit is
0. - Initialization:
min_priceis initialized to the first element of the list. This will keep track of the lowest price seen so far.max_profitis initialized to0. This will store the maximum profit found.
- Iterating through Prices:
- We start iterating from the second price because we can’t sell on the first day.
- For each price, calculate the potential profit by subtracting
min_pricefrom the current price. - If this calculated profit is greater than the current
max_profit, updatemax_profit. - If the current price is less than
min_price, updatemin_price.
- Return Result: After looping through all prices,
max_profitwill contain the maximum possible profit.
This approach ensures that we only pass through the list once, making the solution efficient with a time complexity of O(n).
Solution in Javascript:
JavaScript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
// If there are no prices or only one price, no profit can be made
if (prices.length < 2) {
return 0;
}
// Initialize minimum price to the first price in the list
let minPrice = prices[0];
// Initialize max profit to zero as no transaction has been made yet
let maxProfit = 0;
// Loop through each price starting from the second price
for (let i = 1; i < prices.length; i++) {
let price = prices[i];
// Calculate profit if selling at current price
let profit = price - minPrice;
// Update max profit if current profit is greater
if (profit > maxProfit) {
maxProfit = profit;
}
// Update min price if current price is lower
if (price < minPrice) {
minPrice = price;
}
}
return maxProfit;
};Solution in Java:
Java
class Solution {
public int maxProfit(int[] prices) {
// If there are no prices or only one price, no profit can be made
if (prices == null || prices.length < 2) {
return 0;
}
// Initialize minimum price to the first price in the list
int minPrice = prices[0];
// Initialize max profit to zero as no transaction has been made yet
int maxProfit = 0;
// Loop through each price starting from the second price
for (int i = 1; i < prices.length; i++) {
int price = prices[i];
// Calculate profit if selling at current price
int profit = price - minPrice;
// Update max profit if current profit is greater
if (profit > maxProfit) {
maxProfit = profit;
}
// Update min price if current price is lower
if (price < minPrice) {
minPrice = price;
}
}
return maxProfit;
}
}Solution in C#:
C#
public class Solution {
public int MaxProfit(int[] prices) {
// If there are no prices or only one price, no profit can be made
if (prices == null || prices.Length < 2) {
return 0;
}
// Initialize minimum price to the first price in the list
int minPrice = prices[0];
// Initialize max profit to zero as no transaction has been made yet
int maxProfit = 0;
// Loop through each price starting from the second price
for (int i = 1; i < prices.Length; i++) {
int price = prices[i];
// Calculate profit if selling at current price
int profit = price - minPrice;
// Update max profit if current profit is greater
if (profit > maxProfit) {
maxProfit = profit;
}
// Update min price if current price is lower
if (price < minPrice) {
minPrice = price;
}
}
return maxProfit;
}
}