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

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

編輯:關於C++

一. 題目描述

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 k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

二. 題目分析

這一題的難度要遠高於前面幾題,需要用到動態規劃,代碼參考了博客:http://www.cnblogs.com/grandyang/p/4295761.html

這裡需要兩個遞推公式來分別更新兩個變量localglobal,然後求至少k次交易的最大利潤。我們定義local[i][j]為在到達第i天時最多可進行j次交易並且最後一次交易在最後一天賣出的最大利潤,此為局部最優。然後我們定義global[i][j]為在到達第i天時最多可進行j次交易的最大利潤,此為全局最優。它們的遞推式為:

local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)

global[i][j] = max(local[i][j], global[i - 1][j])

三. 示例代碼

#include 
#include 
#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int maxProfit(int k, vector &prices) {
        if(prices.empty() || k == 0)
          return 0;

        if(k >= prices.size())
          return solveMaxProfit(prices);

        vector global(k + 1, 0);
        vector local(k + 1, 0);

        for(int i = 1; i < prices.size(); i++) {
            int diff = prices[i] - prices[i - 1];
            for(int j = k; j >= 1; j--) {
                local[j] = max(local[j] + diff, global[j - 1] + max(diff, 0));
                global[j] = max(global[j], local[j]);
            }
        }

        return global[k];
    }

private:
    int solveMaxProfit(vector &prices) {
        int res = 0;
        for(int i = 1; i < prices.size(); i++) {
            int diff = prices[i] - prices[i - 1];
            if(diff > 0)
              res += diff;
        }
        return res;
    }
};

 

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