Best Time to Buy and Sell Stock IV股票交易(hard)--力扣101算法题解笔记
7.8Best Time to Buy and Sell Stock IV股票交易(hard)
题目描述
给定一段时间内每天的股价，已知你只可以买卖各k次，且每次只能拥有一支股票，求最大的收益
输入输出样例
Input ：[3, 2, 6, 5, 0, 3] , k = 2
Output：7
最大的利润在第二天价格为2的时候买入，第三天价格为6的时候卖出，在第五天的价格为0时候买入，第六天价格为3的时候卖出。
题解
如果k>总天数，那就一赚钱就卖了，如果k<总天数，就比较麻烦了。
先建立两个动态数组buy和sell，对于每天的股价，buy[j]表示第j次买入时的最大收益，sell[j]表示在第j次卖出时的最大收益。
#include <iostream> #include <vector> #include <climits> using namespace std; /** * @brief 无限次交易的最大利润（当k >= 天数/2时等价于无限次） * @param prices 股价数组（值传递改为引用，提升效率） * @return 最大利润 * 逻辑：只要后一天股价比前一天高，就买入卖出赚差价（贪心策略） */ int maxProfitUnlimited(vector<int>& prices) { int maxProfit = 0; // 初始化最大利润为0 // 遍历每天的股价（从第2天开始，因为要和前一天比较） for (int i = 1; i < prices.size(); ++i) { // 如果当天股价 > 前一天股价，说明能赚钱，累加差价 if (prices[i] > prices[i - 1]) { maxProfit += prices[i] - prices[i - 1]; } } return maxProfit; } /** * @brief 最多k次交易的最大利润（每次只能持有1支股票，先买后卖） * @param k 最大交易次数（买卖算一次完整交易） * @param prices 股价数组（引用传递避免拷贝） * @return 最大收益 * 核心：动态规划，用buy[j]和sell[j]记录第j次交易的状态 */ int maxProfit(int k, vector<int>& prices) { int days = prices.size(); // 总天数 // 边界条件1：天数<2（至少2天才能完成一次买卖），利润为0 if (days < 2) { return 0; } // 边界条件2：k >= 天数/2 → 等价于无限次交易（一次交易至少2天，超过天数/2就无限制） if (k >= days / 2) { return maxProfitUnlimited(prices); } // 动态规划数组定义（核心） // buy[j]：完成第j次买入后，当前持有股票的最大利润（初始INT_MIN表示"不可能持有"） // sell[j]：完成第j次卖出后，当前不持有股票的最大利润（初始0表示"无交易时利润为0"） vector<int> buy(k + 1, INT_MIN), sell(k + 1, 0); // 遍历每一天的股价，更新每一次交易的状态 for (int i = 0; i < days; ++i) { // 遍历每一次交易（从第1次到第k次） for (int j = 1; j <= k; ++j) { // 状态转移1：更新第j次买入的最大利润 // 两种选择： // 1. 不操作：保持之前第j次买入的状态 → buy[j] // 2. 操作：用第j-1次卖出的利润，买入当天的股票 → sell[j-1] - prices[i] // 取两者最大值（追求利润最大化） buy[j] = max(buy[j], sell[j - 1] - prices[i]); // 状态转移2：更新第j次卖出的最大利润（核心修正：原代码是减号，已改为加号） // 两种选择： // 1. 不操作：保持之前第j次卖出的状态 → sell[j] // 2. 操作：卖出第j次买入持有的股票 → buy[j] + prices[i] // 取两者最大值 sell[j] = max(sell[j], buy[j] + prices[i]); } } // 最终结果：完成k次卖出后的最大利润（不持有股票时利润最大） return sell[k]; } int main() { // 测试用例：股价数组 + 最大交易次数k=2 vector<int> prices{ 3,2,6,5,0,3 }; int k = 2; // 输出结果：7（交易1：2买6卖，利润4；交易2：0买3卖，利润3 → 总7） cout << maxProfit(k, prices) << endl; return 0; }