If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Solution1:
public class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2)
return 0;
if (prices.length == 2)
return prices[0] > prices[1] ? 0 : prices[1] - prices[0];
int[] maxAfter = new int[prices.length-1];
maxAfter[maxAfter.length-1] = prices[prices.length-1];
for (int j = maxAfter.length - 2; j >= 0; j--)
maxAfter[j] = maxAfter[j+1] > prices[j+1] ? maxAfter[j+1] : prices[j+1];
int ans = 0;
for (int i = 0; i < maxAfter.length; i++)
ans = (maxAfter[i] - prices[i]) > ans ? (maxAfter[i] - prices[i]) : ans;
return ans;
}
}
Solution2: improved from solution1, space efficient
public class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2)
return 0;
int maxAfter = prices[prices.length-1];
int maxProf = 0;
for (int j = prices.length - 2; j >= 0; j--) {
if (prices[j] < maxAfter) {
int profit = maxAfter - prices[j];
maxProf = profit > maxProf ? profit : maxProf;
}
else
maxAfter = prices[j];
}
return maxProf;
}
}
No comments:
Post a Comment