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. public class Solution {
  4.     public int maxProfit(int[] prices) {
  5.         if (prices.length < 2) return 0;
  7.         final int n = prices.length;
  8.         int[] f = new int[n];
  9.         int[] g = new int[n];
  11.         for (int i = 1, valley = prices[0]; i < n; ++i) {
  12.             valley = Math.min(valley, prices[i]);
  13.             f[i] = Math.max(f[i - 1], prices[i] - valley);
  14.         }
  16.         for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) {
  17.             peak = Math.max(peak, prices[i]);
  18.             g[i] = Math.max(g[i], peak - prices[i]);
  19.         }
  21.         int max_profit = 0;
  22.         for (int i = 0; i < n; ++i)
  23.             max_profit = Math.max(max_profit, f[i] + g[i]);
  25.         return max_profit;
  26.     }
  27. }

相关题目

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