LeetCode-188. Best Time to Buy and Sell Stock IV

LeetCode-188. 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).

Example 1:

Input: [2,4,1], k = 2Output: 2Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2Output: 7Explanation: 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.

题解：

类似123题，但是要处理买卖次数大于股票数一半时候（此时就是无限次买卖问题，只要盈利就买完事了）

class Solution {public: int maxProfit(int k, vector& prices) { int n = prices.size(); if (n < 2 || k < 1) { return 0; } if (k > n / 2) { int res = 0; for (int i = 1; i < n; i++) { if (prices[i] > prices[i - 1]) { res += prices[i] - prices[i - 1]; } } return res; } vector buy(k, 0), sell(k, 0); for (int i = 0; i < k; i++) { buy[i] = -prices[0]; } for (int i = 1; i < n; i++) { for (int j = 0; j < k; j++) { if (j == 0) { buy[j] = max(buy[j], -prices[i]); } else { buy[j] = max(buy[j], sell[j - 1] - prices[i]); } sell[j] = max(sell[j], prices[i] + buy[j]); } } return sell[k - 1]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。