Problem 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.
Python Solution
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
if price < min_price:
min_price = price
else:
max_profit = max(max_profit, price - min_price)
return max_profit
Java Solution
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2)
return 0;
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] < minPrice)
minPrice = prices[i];
else
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
return maxProfit;
}
}
C++ Solution
class Solution {
public:
int maxProfit(vector& prices) {
if (prices.empty())
return 0;
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] < minPrice)
minPrice = prices[i];
else
maxProfit = max(maxProfit, prices[i] - minPrice);
}
return maxProfit;
}
};
JavaScript Solution
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
if (!prices.length)
return 0;
let minPrice = prices[0];
let maxProfit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] < minPrice)
minPrice = prices[i];
else
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
return maxProfit;
};
C# Solution
public class Solution {
public int MaxProfit(int[] prices) {
if (prices == null || prices.Length < 2)
return 0;
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.Length; i++) {
if (prices[i] < minPrice)
minPrice = prices[i];
else
maxProfit = Math.Max(maxProfit, prices[i] - minPrice);
}
return maxProfit;
}
}
Complexity Analysis
- Time Complexity: O(n) where n is the length of the prices array
- Space Complexity: O(1) as we only use two variables
Solution Explanation
This solution uses a single pass through the array with two variables:
minPrice
: Keeps track of the minimum price seen so farmaxProfit
: Keeps track of the maximum profit we can achieve
For each price, we either:
- Update the minimum price if we find a lower price
- Calculate the potential profit if we sell at the current price and update maxProfit if it's higher
This approach ensures we're always buying at the lowest price seen so far and calculating the maximum possible profit we could make by selling at the current price.