Android教程網
  1. 首頁
  2. Android 技術
  3. Android 手機
  4. Android 系統教程
  5. Android 游戲
 Android教程網 >> Android技術 >> 關於Android編程 >> Leetcode Best Time to Buy and Sell Stock III

Leetcode Best Time to Buy and Sell Stock III

編輯:關於Android編程

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).

要掌握這種思想:

1 兩段分段思想
2 前往後,後往前都可以處理數列的思想

時間復雜度是O(n),不掌握這種思想是很難做出來的。

class Solution {
public:
    int maxProfit(vector &prices) 
	{
		vector profit(prices.size()+1);

		int buy = INT_MAX;
		for (int i = 0; i < prices.size(); i++)
		{
			if (prices[i] < buy) buy = prices[i];
			else profit[i+1] = max(profit[i], prices[i]-buy);
		}

		int sale = INT_MIN , max_profit = 0, res = 0;
		for (int i = prices.size() - 1; i >= 0 ; i--)
		{
			if (prices[i] > sale) sale = prices[i];
			else max_profit = max(max_profit, sale - prices[i]);
			profit[i+1] = profit[i+1]+ max_profit;
			res = max(profit[i+1], res);
		}
		return res;
	}
};


  1. 上一頁:
  2. 下一頁:
熱門文章
閱讀排行版
Copyright © Android教程網 All Rights Reserved