本节包含
121 Best Time to Buy and Sell Stock
122 Best Time to Buy and Sell Stock II
123 Best Time to Buy and Sell Stock III
188 Best Time to Buy and Sell Stock IV
Best Time to Buy and Sell Stock 1
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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
买卖股票有个隐含条件是，买的日期肯定在卖的日期之前。我们可以用2个变量来分别表示，minBuyPrice和maxProfit。
用一个循环遍历数组：
- 初始条件是minBuyPrice是
prices[0], 而当天卖出价与买进价是一样的，所以当前的maxProft是0。 - 一旦遇到
prices[i]小于minBuyPrice，那么更新minBuyPrice，继续遍历。 - maxProfit ：
max(prices[i] - minBuyPrice)，继续遍历。
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int minBuyingPrice = prices[0];
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
minBuyingPrice = Math.min(minBuyingPrice, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - minBuyingPrice);
}
return maxProfit;
}
}
Best Time to Buy and Sell Stock 2
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
整个过程可以买卖很多次，但是每天只能买或者卖
比如
1， 2， 5， 6， 4， 5
diff： 1 3 1 -2 1
其实就是求股票低价买，高价卖最多能获得多少钱。求连续上升的高度和。
所以maxProfit就是所有diff>0的值相加。只要prices[i] - prices[i-1]>0，就在第i-1天买入，第i天抛出。这样可以包括所有可能赚取利润的区间。
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int result = 0;
for (int i = 1; i < prices.length; i++) {
result = result + (prices[i] - prices[i - 1] > 0 ? prices[i] - prices[i - 1] : 0);
}
return result;
}
}
