Practice › Arrays
Best Time to Buy and Sell Stock
Easy · Arrays · Asked at Amazon, Microsoft, Google, Goldman Sachs, Flipkart
price[i] is the stock price on day i. Buy on one day and sell on a later day. Print the maximum profit, or 0 if no profit is possible.
Input
First line: n. Second line: n space-separated integers.
Output
The maximum profit.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ price[i] ≤ 10^4
Example 1
Input
6 7 1 5 3 6 4
Output
5
Example 2
Input
5 7 6 4 3 1
Output
0
Hints
- If you sell on day i, the best buying day is the cheapest day before it.
- Track the minimum price seen so far and the best profit price[i] − minimum.
Approach
Scan left to right, keeping the lowest price so far. On each day, selling today earns price − lowest; keep the largest such profit. The profit never goes below 0 because the minimum includes today's price.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int lowest = INT_MAX, best = 0, p;
for (int i = 0; i < n; i++) {
cin >> p;
lowest = min(lowest, p);
best = max(best, p - lowest);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
lowest, best = float("inf"), 0
for p in data[1 : data[0] + 1]:
lowest = min(lowest, p)
best = max(best, p - lowest)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), lowest = Integer.MAX_VALUE, best = 0;
for (int i = 0; i < n; i++) {
int p = sc.nextInt();
lowest = Math.min(lowest, p);
best = Math.max(best, p - lowest);
}
System.out.println(best);
}
}Solve Best Time to Buy and Sell Stock online · All practice problems