using System; using System.Collections.Generic; class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @return int整型 */ public int maxProfit (List<int> prices) { // write code here int profit=0; int buy=0; int sale=0; while(sale<prices.Count) { int curProfit=prices[sale]-prices[buy]; profit=Math.Max(profit, curProfit); if(curProfit<0) { buy=sale; } sale++; } return profit; } }
将每天的价格前后相减,可以得到每天的收益,如果从某天买入时,收益总和为负数,那么就需要更新买入时间。
例如[8 9 2 5 4 7 1]
作差为:
[1 -7 3 -1 3 -6]
等价于寻找连续子序列和最大的。
第二天涨了一元,但是第三天跌了7元,所以无论后面什么价格,都不该在第一天买,而是在更低的第三天买,第四天涨了3元,虽然第五天跌了一元,但是总体还是赚的,没必要更新买入点
(可以理解为)牛市的小波动,果然第六天又涨了3元,最后一天大跌,所以最佳抛售时间是第六天。