Best time to buy and sell stocks IV

题目

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

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.

Solution

• global(n, k) 表示前n天中一共进行k次交易，所能获取到的最大收益
• local(n, k) 表示前n中一共进行k次交易，且最后一次卖出发生在第n天，所能获取的最大收益

于是就有递推式子如下：

• global(n, k) = max(local(n, k), global(n-1, k));
  两种情况：
  1，最后一天卖出
  2，最后一天没有卖出

• local(n, k) = max(local(n-1, k)+diff, global(n-1, k-1), global(n-1,k-1)+diff);
  三种情况：
  1，第n-1天卖出，并且第n-1天买入，然后第n天卖出，那虽然是k+1次交易，但是最后两次交易可以合并成一次，因此也算是k次交易
  2，前n-1天内已经进行了k-1次交易，然后第n天买入，并卖出
  3，前n-1天内进行了k-1次交易，然后第n-1天买入，第n天卖出