Best Time to Buy and Sell Stock IV

描述

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

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

分析

设两个状态，global[i][j] 表示i天前最多可以进行j次交易的最大利润，local[i][j]表示i天前最多可以进行j次交易，且在第i天进行了第j次交易的最大利润。状态转移方程如下：

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

关于global的状态转移方程比较简单，不断地和已经计算出的local进行比较，把大的保存在global中。

关于local的状态转移方程，取下面二者中较大的一个：

  • 全局前i-1天进行了j-1次交易，然后然后加上今天的交易产生的利润（如果赚钱就交易，不赚钱就不交易，什么也不发生，利润是0）
  • 局部前i-1天进行了j次交易，然后加上今天的差价（local[i-1][j]是第i-1天卖出的交易，它加上diff后变成第i天卖出，并不会增加交易次数。无论diff是正还是负都要加上，否则就不满足local[i][j]必须在最后一天卖出的条件了）
    注意，当k大于数组的大小时，上述算法将变得低效，此时可以改为不限交易次数的方式解决，即等价于 "Best Time to Buy and Sell Stock II"。

解法1

  1. // Best Time to Buy and Sell Stock IV
  2. // Time Complexity: O(nk), Space Complexity: O(nk)
  3. public class Solution {
  4.     public int maxProfit(final int k, final int[] prices) {
  5.         if (prices.length < 2 || k < 1) return 0;
  6.         if (k >= prices.length) return maxProfit(prices);
  8.         final int[][] local = new int[prices.length][k + 1];
  9.         final int[][] global = new int[prices.length][k + 1];
  11.         for (int i = 1; i < prices.length; i++) {
  12.             final int diff = prices[i] - prices[i - 1];
  13.             for (int j = 1; j < k+1; j++) {
  14.                 local[i][j] = Math.max(
  15.                         global[i - 1][j - 1] + Math.max(diff, 0),
  16.                         local[i - 1][j] + diff);
  17.                 global[i][j] = Math.max(global[i - 1][j], local[i][j]);
  18.             }
  19.         }
  21.         return global[prices.length - 1][k];
  22.     }
  24.     // Best Time to Buy and Sell Stock II
  25.     public static int maxProfit(final int[] prices) {
  26.         int sum = 0;
  27.         for (int i = 1; i < prices.length; i++) {
  28.             int diff = prices[i] - prices[i - 1];
  29.             if (diff > 0) sum += diff;
  30.         }
  31.         return sum;
  32.     }
  33. }

解法2 最长m段子段和

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