You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1] Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3] Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Constraints:
0 <= k <= 1000 <= prices.length <= 10000 <= prices[i] <= 1000
Solution: DP
profit[i][j] := max profit by making up to j sells in first i days. (Do not hold any share)
balance[i][j] := max balance by making at to up j buys in first i days. (Most hold a share)
balance[i][j] = max(balance[i-1][j], profit[i-1][j-1] – prices[i]) // do nothing or buy at i-th day.
profit[i][j] = max(profit[i-1][j], balance[i-1][j] + prices[i]) // do nothing or sell at i-th day.
ans = profit[n-1][k]
Time complexity: O(n*k)
Space complexity: O(k)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int maxProfit(int k, vector<int>& prices) { const int n = prices.size(); vector<int> balance(k + 1, INT_MIN); vector<int> profit(k + 1, 0); for (int i = 0; i < n; ++i) for (int j = 1; j <= k; ++j) { balance[j] = max(balance[j], profit[j - 1] - prices[i]); profit[j] = max(profit[j], balance[j] + prices[i]); } return profit[k]; } }; |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment