蓝一互动网站建设,网站做的不满意,sem竞价托管多少钱,做网站一年多少钱算法刷题记录 Day43
Date: 2024.04.10
lc 188. 买卖股票的最佳时机IV
// 拓展一下lc.123 的思路即可.
class Solution {
public:int maxProfit(int k, vectorint prices) {int n prices.size();//dp[i] 表示 第i天时完成不同笔交易下的各状态。[buy_1, sell_1…算法刷题记录 Day43
Date: 2024.04.10
lc 188. 买卖股票的最佳时机IV
// 拓展一下lc.123 的思路即可.
class Solution {
public:int maxProfit(int k, vectorint prices) {int n prices.size();//dp[i] 表示 第i天时完成不同笔交易下的各状态。[buy_1, sell_1, ..., buy_k, sell_k]vectorint dp(2*k, 0);// 初始化for(int j2*k-2; j0; jj-2){ dp[j1] 0;dp[j] -prices[0];}for(int i1; in; i){for(int j2*k-2; j0; jj-2){ dp[j1] max(dp[j1], dp[j]prices[i]); // max(sell_k, buy_k prices[i]);if(j 0)dp[j] max(dp[j], dp[j-1]-prices[i]); // max(buy_k, sell_{k-1} - prices[i]);elsedp[j] max(dp[j], -prices[i]);}}int max_res INT_MIN;for(int j2*k-2; j0; jj-2){ max_res max(max_res, dp[j1]);}return max_res;}
};lc 123. 买卖股票的最佳时机III
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();// 任意一天结束后我们会处在五种状态中的一种.记录当前的现金数。// 1.无操作2.进行了一次购买3.进行了一次购买卖出4.进行了买卖购买5.完成了两次买卖// 1. 无操作不管// 2. 进行了一次购买buy_1 max(prices[i], buy_1);// 3. 进行了一次买卖sell_1 max(sell_1, prices[i] buy_1); //此处buy_1未更新// 4. 进行了买卖购买buy_2 max(buy_2, sell_1 - prices[i]); // 此处sell1未更新// 5. 完成了两次买卖: sell_2 max(sell_2, buy_2 prices[i]);// 初始化 buy_1和buy_2为购买了第一天的情况sell_1和sell_2为0无交易时的当前现金。int buy_1 -prices[0];int sell_1 0;int buy_2 -prices[0];int sell_2 0;for(int i1; in; i){sell_2 max(sell_2, buy_2 prices[i]);buy_2 max(buy_2, sell_1 - prices[i]);sell_1 max(sell_1, prices[i] buy_1);buy_1 max(-prices[i], buy_1);}if(sell_2 0)return 0;elsereturn sell_2;}
};
