LeetCode 121 买卖股票的最佳时机

1.自己的做法

class Solution { public int maxProfit(int[] prices) { if(prices.length==0) return 0; int in=prices[0],out=0; for(int i=1;i<prices.length;i++){ if(prices[i]>in&&prices[i]-in>out){ out=prices[i]-in; }else if(prices[i]<in){ in=prices[i]; } } return out; } }

1.in表示买入的那一天买入的价格，out表示在某天卖出的收益

2.在循环的过程中，设in的初值为第一天的价格，如果i天的价格大于in，就计算收益是否大于out，大于就更新，i天的价格小于in，就把这一天当做in，更新in

2.dp动态规划

class Solution { public int maxProfit(int[] prices) { if(prices.length==0) return 0; int dp_i_0=0,dp_i_1=Integer.MIN_VALUE; for(int i=0;i<prices.length;i++){ dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]); dp_i_1=Math.max(dp_i_1,-prices[i]); } return dp_i_0; } }

 

 这个题我也很难说清楚，从最开始的动态规划，到初始值的设定，很复杂，有个题解写的很好

非常棒、细致的题解