LeetCode 188. Best Time to Buy and Sell Stock IV

问题描述
【LeetCode 188. Best Time to Buy and Sell Stock IV】LeetCode 188. Best Time to Buy and Sell Stock IV
文章图片

  • 地址
问题分析
  • 假设可以最多进行 k次交易,那么求能获得的最大利益
  • 利用动态规划解题:首先明确两个状态的意义:
    • local[i][j] : 第i天正好完成了j次交易的最大利益
    • global[i][j] : 前i天完成了j次交易的最大利益
  • 递归关系:
    • local[j] = Math.max(local[j] + diff, global[j - 1] + Math.max(diff, 0));
    • global[j] = Math.max(global[j], local[j]);
  • 注意:
    • k >= len/2时,便等同于无限次交易 122. Best Time to Buy and Sell Stock II
    • k = 2 时,便是 123. Best Time to Buy and Sell Stock III
代码实现
  • 原始动态规划
//local[i][j] : 第i天正好完成了j次交易的最大利益 //global[i][j] : 前i天完成了j次交易的最大利益 public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0 || k <= 0) { return 0; } int len = prices.length; int[][] local = new int[len][k + 1]; int[][] global = new int[len][k + 1]; for (int i = 1; i < len; ++i) { int diff = prices[i] - prices[i - 1]; //local[i][0] = 0; for (int j = 1; j < k + 1; ++j) { local[i][j] = Math.max(local[i - 1][j] + diff, global[i - 1][j - 1] + Math.max(diff, 0)); global[i][j] = Math.max(global[i - 1][j], local[i][j]); } } return global[len - 1][k]; }

  • 动态规划优化空间
public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0 || k <= 0) { return 0; } int len = prices.length; if(k >= len / 2){ int sum = 0; for(int i = 1; i < prices.length; i++){ if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1]; } return sum; } int[] local = new int[k + 1]; int[] global = new int[k + 1]; for (int i = 1; i < len; ++i) { int diff = prices[i] - prices[i - 1]; //local[0] = 0; for (int j = k; j > 0; --j) { local[j] = Math.max(local[j] + diff, global[j - 1] + Math.max(diff, 0)); global[j] = Math.max(global[j], local[j]); } } return global[k]; }

    推荐阅读