程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Best Time to Buy and Sell Stock III

leetcode筆記:Best Time to Buy and Sell Stock III

編輯:C++入門知識

leetcode筆記:Best Time to Buy and Sell Stock III


一. 題目描述

Say you have an array for which the i-th 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]中的最大利潤profit,用一個數組f1保存下來,這一步時間復雜度為O(n)

第二步是逆向掃描,計算子序列[i, …, n - 1]中的最大利潤profit,同樣用一個數組f2保存下來,這一步的時間復雜度也是O(n)

最後一步,對於,對f1 + f2,找出最大值即可。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    int maxProfit(vector &prices) 
    {
        int size = prices.size();
        if (size <= 1) return 0;

        vector f1(size);
        vector f2(size);

        int minV = prices[0];
        for (int i = 1; i < size; ++i)
        {
            minV = std::min(minV, prices[i]);
            f1[i] = std::max(f1[i - 1], prices[i] - minV);
        }

        int maxV = prices[size - 1];
        f2[size - 1] = 0;
        for (int i = size-2; i >= 0; --i)
        {
            maxV = std::max(maxV, prices[i]);
            f2[i] = std::max(f2[i + 1], maxV - prices[i]);
        }

        int sum = 0;
        for (int i = 0; i < size; ++i)
            sum = std::max(sum, f1[i] + f2[i]);

        return sum;
    }
};

四. 小結

相比前兩題,該題難度稍大,與該題相關的題目有好幾道。後續更新…

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved