Maximize Price Difference — Problem Statement & Solution Guide
Problem Description
You are given an array of integers prices representing daily stock prices. Find the maximum possible return you can achieve by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Note that the day you buy must be before the day you sell.
Examples
Input
[7,1,5,3,6,4]
Output
5
Explanation: Step-by-step: with input [7,1,5,3,6,4], we find the minimum price on day 2 which is 1. Then we find the maximum price after day 2 which is 6 on day 5. This gives us a maximum possible return of 6 - 1 = 5. We can also get a return of 5 by buying on day 0 and selling on day 5.
Input
[7,6,4,3,1]
Output
0
Explanation: Step-by-step: with input [7,6,4,3,1], the prices are decreasing every day. This means we cannot sell for a higher price than we buy. Therefore, the maximum possible return is 0. We can also get a return of 0 by buying on day 4 and selling on day 4.
Constraints
- 2 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^4
Optimal Approach & Strategy
The optimized approach involves iterating through the array once to find the maximum return. This approach has a linear time complexity and is efficient for large inputs. It can be implemented using a single loop to keep track of the minimum price and the maximum return seen so far.
Brute Force Approach
The brute force approach involves checking every possible buying and selling price combination. This approach has a high time complexity and is not efficient for large inputs. It can be implemented using nested loops to compare each pair of prices.
Verified Code Solutions
function maxReturn(prices) {
if (prices.length < 2) return 0;
let minPrice = prices[0];
let maxReturn = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxReturn) {
maxReturn = prices[i] - minPrice;
}
}
return maxReturn;
}#include <iostream>
#include <vector>
using namespace std;
int maxReturn(vector<int>& prices) {
if (prices.size() < 2) return 0;
int minPrice = prices[0];
int maxReturn = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxReturn) {
maxReturn = prices[i] - minPrice;
}
}
return maxReturn;
}
int main() {
vector<int> prices = {10, 7, 5, 8, 11, 9};
cout << maxReturn(prices) << endl;
return 0;
}class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}
int min_price = prices[0];
int max_profit = 0;
for (int price : prices) {
if (price < min_price) {
min_price = price;
} else if (price - min_price > max_profit) {
max_profit = price - min_price;
}
}
return max_profit;
}
}def maxProfit(prices):
if len(prices) < 2:
return 0
min_price = prices[0]
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profitfunction maxReturn(prices) {
if (prices.length < 2) return 0;
let minPrice = prices[0];
let maxReturn = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxReturn) {
maxReturn = prices[i] - minPrice;
}
}
return maxReturn;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.