LeetCode - Best Time to Buy and Sell Stock
Problem description
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
1
2
3
4
Input: [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.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Analysis
Generally, we can use a variable to save the price to buy, and if the current price is bigger than the price, we sell it and update max profit. If the current price is lower than the buy price, we update the buy price to the lower one. Since if there are a higher price to sell, buy in a lower price will get the max profit.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0){
return 0;
}
int max = 0;
int buy = prices[0];
int cur = 0;
for (int i: prices){
if (i < buy){
buy = i;
}
else{
cur = Math.max(i - buy, cur);
max = Math.max(max, cur);
}
}
return max;
}