- Best Time to Buy and Sell Stock
只能买卖一次。
只能一次的话，就是要寻找最小和最大的值（同时必须满足最大值在最小值后面）
可以用两个值来存,maxcurr记录对于第i天可以拿到的最大利润，maxsofar记录到目前为止见过的最大利润（最大的maxcurr)。
所以唯一的问题是如何计算maxcurr，如果maxcurr小于0，那么就是0，对于第i天的maxcurr来说，如果maxcurr + (p[i] - p[i-1]) > 0, 那么更新maxcurr。
或者可以，一直寻找最小的minprice，然后用prices[i]-minprice，同时即时更新minprice。
code1:
public class Solution {
public int maxProfit(int[] prices) {
int maxcurr = 0;
int maxsofar = 0;
for (int i = 1; i < prices.length; i++) {
maxcurr = Math.max(0, maxcurr + (prices[i] - prices[i-1]));
maxsofar = Math.max(maxsofar, maxcurr);
}
return maxsofar;
}
}
code2:
public int maxProfit(int[] prices) {
int profit = 0;
int minElement = Integer.MAX_VALUE;
for(int i=0; i < prices.length; i++){
profit = Math.max(profit, prices[i]-minElement);
minElement = Math.min(minElement, prices[i]);
}
return profit;
}
- Best Time to Buy and Sell Stock II
可以买卖多次。这样的话很容易理解，就是把所以递增的都增量都加起来就可以了。因为如果是递增，那么price[j] - price[k] = price[j]-price[i] + price[i]-price[k]
public class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}
int total = 0;
for (int i = 1; i < prices.length; i++) {
total += Math.max(0, prices[i] - prices[i-1]);
}
return total;
}
}
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Best Time to Buy and Sell Stock with Cooldown
