![]()
![]()
————— 第二天 —————
![]()
![]()
![]()
![]()
![]()
![]()
什么意思呢？让我们来举个例子，给定如下数组：
![]()
该数组对应的股票涨跌曲线如下：
![]()
显然，从第2天价格为1的时候买入，从第5天价格为8的时候卖出，可以获得最大收益：
![]()
此时的最大收益是 8-1=7。
![]()
![]()
![]()
![]()
![]()
在上面这个例子中，最大值9在最小值1的前面，我们又该怎么交易？总不能让时间倒流吧？
![]()
![]()
————————————
![]()
![]()
![]()
![]()
![]()
![]()
以下图为例，假如我们已经确定价格4的时候为卖出时间点，那么此时最佳的买入时间点是哪一个呢？
![]()
我们要选择价格4之前的区间，且必须是区间内最小值，显然，这个最佳的选择是价格2的时间点。
![]()
![]()
第1步，初始化操作，把数组的第1个元素当做临时的最小价格；最大收益的初始值是0：
![]()
第2步，遍历到第2个元素，由于2<9，所以当前的最小价格变成了2；此时没有必要计算差值的必要（因为前面的元素比它大），当前的最大收益仍然是0：
![]()
第3步，遍历到第3个元素，由于7>2，所以当前的最小价格仍然是2；如我们刚才所讲，假设价格7为卖出点，对应的最佳买入点是价格2，两者差值7-2=5，5>0，所以当前的最大收益变成了5：
![]()
第4步，遍历到第4个元素，由于4>2，所以当前的最小价格仍然是2；4-2=2，2<5，所以当前的最大收益仍然是5：
![]()
第5步，遍历到第5个元素，由于3>2，所以当前的最小价格仍然是2；3-2=1，1<5，所以当前的最大收益仍然是5：
![]()
以此类推，我们一直遍历到数组末尾，此时的最小价格是1；最大收益是8-1=7：
![]()
![]()
![]()
public class StockProfit {
public static int maxProfitFor1Time(int prices[]) {
if(prices==null || prices.length==0) {
return 0;
}
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if(prices[i] - minPrice > maxProfit){
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices = {9,2,7,4,3,1,8,4};
System.out.println(maxProfitFor1Time(prices));
}
}
![]()
![]()
![]()
![]()
![]()
我们以下图这个数组为例，直观地看一下买入卖出的时机：
![]()
在图中，绿色的线段代表价格上涨的阶段。既然买卖次数不限，那么我们完全可以在每一次低点都进行买入，在每一次高点都进行卖出。
这样一来，所有绿色的部分都是我们的收益，最大总收益就是这些局部收益的加总：
（6-1）+（8-3）+（4-2）+（7-4） = 15
至于如何判断出这些绿色上涨阶段呢？很简单，我们遍历整个数组，但凡后一个元素大于前一个元素，就代表股价处于上涨阶段。
![]()
public int maxProfitForAnyTime(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1])
maxProfit += prices[i] - prices[i-1];
}
return maxProfit;
}
![]()
![]()
![]()
![]()
![]()
—————END—————
喜欢本文的朋友，欢迎关注公众号 程序员小灰，收看更多精彩内容
![]()
