第四周主题：Decrease and Conquer (减治法) 之 Best Time to Buy and Sell Stock III in LeetCode (in java)

题目：

http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/


要求：

 /**

  * 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 at most

  * two transactions.

  * 

  * Note: You may not engage in multiple transactions at the same time (ie,

  * you must sell the stock before you buy again).

  */
(找出对某只股票能获得的最大收益，最多只能买卖两次，买了之后才能卖，卖了第一次之后才能买第二次)



解答：

分两步，分别找出在[0,i]和[i,n-1]之间的最大收益，[0,i]正序查找, [i,n-1]逆序查找，这样对于某个特定点i来说，[0,i]和[i,n-1]区间不会重合。
(0)

int[] maxProfits = new int[prices.length]; // save the max profits
maxProfits[0] = 0;

int minPrice = prices[0];
  int maxProfit = 0;
  int profit = 0;
  for (int i = 1; i < prices.length; i++) {
   profit = prices[i] - minPrice;
   if (profit > maxProfit){  //比较最大收益
    maxProfit = profit;
   }
   maxProfits[i] = maxProfit;
   if (prices[i] < minPrice){ //比较价格最小值
    minPrice = prices[i];
   }
  }

(2)

int both = maxProfits[prices.length-1];
  int maxPrice = prices[prices.length-1];
  maxProfit = 0;
  int temp = 0; //临时存放当前两次交易的最大收益
  for (int i = prices.length-2; i>=0; i--) {
   profit = maxPrice - prices[i]; 
   if (profit > maxProfit){ //比较最大收益
    maxProfit = profit;
   }
   temp = maxProfit + maxProfits[i];
   if (temp > both){
    both = temp;
   }
   if (prices[i] > maxPrice){ //比较价格最大值
    maxPrice = prices[i];
   }   
  }

最后return both

References:

[1] 代码在

https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/BestTimeToBuyAndSellStockIII.java