貪心算法leetcode 122

首先放上自己一開始的第一個解：

int start = prices[0];
  int end = prices[0];
  int count = 0;
  for (int i = 1; i < prices.length; i++) {
      if (prices[i] < end) {count += end-start;start = prices[i];end = prices[i];}
      else end = prices[i];
  }
  return count+= end-start;      

定義了一個count用來存放利潤總額。start和end用來表示一個遞增序列的開始和末尾。一發現遞增序列結束，就把這個內插補點加到利潤裡面。

沒想到，這個start和end其實是不必要的。自以為了解了貪心算法的”局部最優推導到全局最優“， 但是沒想到自己的這個局部還不算是最局部的。實際上，隻要兩個數的內插補點是正的，加到利潤裡面就對了。

if(prices.length==0)
        {
            return  0;
        }
        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;