Maximum Profit from Stock Prices — Problem Statement & Solution Guide
Problem Description
You are given an integer array prices of length n, where prices[i] represents the stock price on day i (0‑indexed). A query provides two indices L and R with 0 ≤ L < R < n, defining a contiguous sub‑range of days. Your task is to compute the maximum achievable profit by performing exactly one buy and one sell operation entirely inside the interval [L,R]. The buy must occur before the sell (i < j). If no pair yields a positive profit, return 0. Input consists of n, the array prices, and the pair L R. Output the maximum profit as a single integer.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Profit from Stock Prices"
WHY DOES IT MATTER?
This pattern is essential for handling range queries efficiently, which is a common requirement in financial systems, real-time analytics, and distributed databases. It demonstrates the ability to preprocess data to answer complex queries quickly.
OPTIMIZATION CHALLENGE
The key insight is decomposing the problem into segments and precomputing min, max, and max profit. This reduces the query time from O(N) to O(log N) or O(1).
REAL-WORLD CONNECTION
In stock trading platforms, users often request historical performance metrics for specific date ranges. Efficient range queries ensure low latency and high throughput, critical for real-time trading applications.
During interviews, clearly articulate the trade-off between preprocessing time and query time. Mention that Segment Trees are versatile for both static and dynamic arrays, while Sparse Tables are faster for static arrays but lack update support.
COMPLEXITY AT A GLANCE
O(N + Q log N)O(N)Core Theory — Why This Approach?
The problem of finding the maximum profit in a subarray [L, R] is a classic range query problem. A naive approach would iterate through the subarray for each query, resulting in O(N) time per query, which is inefficient for large N and Q. The optimal paradigm involves preprocessing the array to answer queries in O(1) or O(log N) time. This is typically achieved using a Segment Tree or a Sparse Table, where each node stores the minimum price, maximum price, and the maximum profit within that segment. The key insight is that the maximum profit in a combined segment [L, R] is the maximum of the profits in the left half, the right half, and the cross-boundary profit (max price in right half - min price in left half).
Interview Questions on This Problem
Q1How would you handle multiple queries efficiently if the array is static?
Use a Segment Tree or Sparse Table. Preprocess the array to store min, max, and max profit for each segment. Each query can then be answered in O(log N) time by combining results from relevant segments.
Q2What if the array is dynamic and prices can be updated?
A Segment Tree is preferred over a Sparse Table because it supports point updates in O(log N) time. The Sparse Table is only suitable for static arrays.
Q3Can you explain the cross-boundary profit calculation in the Segment Tree merge step?
When merging two segments, the cross-boundary profit is calculated as (max price in the right segment) - (min price in the left segment). This ensures that the buy happens in the left segment and the sell in the right segment.
Examples
Input
7 8 1 5 3 6 4 7 1 5
Output
5
Explanation: The sub‑range [1,5] covers prices [1,5,3,6,4]. Buying at day 1 (price 1) and selling at day 4 (price 6) yields profit 6‑1 = 5, which is maximal.
Input
5 9 7 4 3 2 0 4
Output
0
Explanation: All prices in the full range are decreasing, so any buy‑sell pair would lose money. The best achievable profit is 0 (no transaction).
Input
6 3 8 2 5 1 9 2 5
Output
8
Explanation: The interval [2,5] contains prices [2,5,1,9]. The optimal choice is to buy at day 4 (price 1) and sell at day 5 (price 9), giving profit 9‑1 = 8.
Constraints
- 1 <= n <= 100000
- -1000000000 <= prices[i] <= 1000000000
- 0 <= L < R < n
Optimal Approach & Strategy
Preprocess the array using a Segment Tree where each node stores min, max, and max profit. For each query, combine segments to compute the result in O(log N) time. This ensures efficient handling of multiple queries.
Brute Force Approach
For each query, iterate through the subarray [L, R] to find the minimum price and the maximum price after the minimum. This results in O(N) time per query, which is too slow for large inputs.
Verified Code Solutions
function maxProfit(prices, L, R) {
if (R - L < 1) return 0;
let minPrice = prices[L];
let maxProfit = 0;
for (let i = L + 1; i <= R; i++) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfit;
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
let lineCount = 0;
rl.on('line', (line) => {
lines.push(line);
lineCount++;
if (lineCount === 3) {
const n = parseInt(lines[0]);
const prices = lines[1].split(' ').map(Number);
const [L, R] = lines[2].split(' ').map(Number);
console.log(maxProfit(prices, L, R));
rl.close();
}
});#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxProfit(const vector<int>& prices, int L, int R) {
if (R - L < 1) return 0;
int minPrice = prices[L];
int maxProfit = 0;
for (int i = L + 1; i <= R; i++) {
maxProfit = max(maxProfit, prices[i] - minPrice);
minPrice = min(minPrice, prices[i]);
}
return maxProfit;
}
int main() {
int n;
cin >> n;
vector<int> prices(n);
for (int i = 0; i < n; i++) {
cin >> prices[i];
}
int L, R;
cin >> L >> R;
cout << maxProfit(prices, L, R) << endl;
return 0;
}import java.util.*;
public class Main {
public static int maxProfit(int[] prices, int L, int R) {
if (R - L < 1) return 0;
int minPrice = prices[L];
int maxProfit = 0;
for (int i = L + 1; i <= R; i++) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfit;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
prices[i] = scanner.nextInt();
}
int L = scanner.nextInt();
int R = scanner.nextInt();
System.out.println(maxProfit(prices, L, R));
scanner.close();
}
}def max_profit(prices, L, R):
if R - L < 1:
return 0
min_price = prices[L]
max_profit = 0
for i in range(L + 1, R + 1):
max_profit = max(max_profit, prices[i] - min_price)
min_price = min(min_price, prices[i])
return max_profit
if __name__ == "__main__":
n = int(input())
prices = list(map(int, input().split()))
L, R = map(int, input().split())
print(max_profit(prices, L, R))function maxProfit(prices, L, R) {
if (R - L < 1) return 0;
let minPrice = prices[L];
let maxProfit = 0;
for (let i = L + 1; i <= R; i++) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfit;
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
let lineCount = 0;
rl.on('line', (line) => {
lines.push(line);
lineCount++;
if (lineCount === 3) {
const n = parseInt(lines[0]);
const prices = lines[1].split(' ').map(Number);
const [L, R] = lines[2].split(' ').map(Number);
console.log(maxProfit(prices, L, R));
rl.close();
}
});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.