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

分析

设状态f(i)，表示区间[0,i](0≤i≤n−1)0,i的最大利润，状态g(i)，表示区间[i,n−1](0≤i≤n−1)i, n-1的最大利润，则最终答案为max{f(i)+g(i)},0≤i≤n−1\max\left{f(i)+g(i)\right},0 \leq i \leq n-1。

允许在一天内买进又卖出，相当于不交易，因为题目的规定是最多两次，而不是一定要两次。

将原数组变成差分数组，本题也可以看做是最大m子段和，m=2，参考代码：https://gist.github.com/soulmachine/5906637

代码

  1. // Best Time to Buy and Sell Stock III
  2. // 时间复杂度O(n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     int maxProfit(vector<int>& prices) {
  6.         if (prices.size() < 2) return 0;
  8.         const int n = prices.size();
  9.         vector<int> f(n, 0);
  10.         vector<int> g(n, 0);
  12.         for (int i = 1, valley = prices[0]; i < n; ++i) {
  13.             valley = min(valley, prices[i]);
  14.             f[i] = max(f[i - 1], prices[i] - valley);
  15.         }
  17.         for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) {
  18.             peak = max(peak, prices[i]);
  19.             g[i] = max(g[i], peak - prices[i]);
  20.         }
  22.         int max_profit = 0;
  23.         for (int i = 0; i < n; ++i)
  24.             max_profit = max(max_profit, f[i] + g[i]);
  26.         return max_profit;
  27.     }
  28. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/dp/best-time-to-buy-and-sell-stock-iii.html