[LeetCode] Best Time to Buy and Sell Stock IV

简介: An extension of Best Time to Buy and Sell Stock III. The idea is still to use dynamic programming (see here for detailed introduction).

An extension of Best Time to Buy and Sell Stock III. The idea is still to use dynamic programming (see here for detailed introduction). However, in this problem, some trick (the quickProfit function below) is required to pass the TLE.

The code is rewritten below.

 1 class Solution {
 2 public:
 3     int maxProfit(int k, vector<int>& prices) {
 4         int n = prices.size();
 5         if (k >= n / 2) return quickProfit(prices);
 6         vector<vector<int> > dp(k + 1, vector<int>(n, 0));
 7         for (int i = 1; i <= k; i++) {
 8             int temp = dp[i - 1][0] - prices[0];
 9             for (int j = 1; j < n; j++) {
10                 dp[i][j] = max(dp[i][j - 1], prices[j] + temp);
11                 temp = max(temp, dp[i - 1][j] - prices[j]);
12             }
13         }
14         return dp[k][n - 1];
15     }
16 private:
17     int quickProfit(vector<int>& prices) {
18         int n = prices.size(), profit = 0;
19         for (int i = 1; i < n; i++)
20             if (prices[i] > prices[i - 1])
21                 profit += prices[i] - prices[i - 1];
22         return profit;
23     }
24 };

 

目录
相关文章
|
6月前
leetcode-1345:跳跃游戏 IV
leetcode-1345:跳跃游戏 IV
45 0
|
3月前
|
算法
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
61 0
|
5月前
|
存储 算法 数据可视化
LeetCode 力扣题目:买卖股票的最佳时机 IV
LeetCode 力扣题目:买卖股票的最佳时机 IV
|
6月前
|
算法
leetcode代码记录(买卖股票的最佳时机 IV
leetcode代码记录(买卖股票的最佳时机 IV
37 2
|
5月前
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
|
6月前
|
SQL
leetcode-SQL-550. 游戏玩法分析 IV
leetcode-SQL-550. 游戏玩法分析 IV
48 1
|
6月前
代码随想录Day42 动态规划10 LeetCode T123 买卖股票的最佳时机III T188买卖股票的最佳时机IV
代码随想录Day42 动态规划10 LeetCode T123 买卖股票的最佳时机III T188买卖股票的最佳时机IV
45 0
|
6月前
|
测试技术
代码随想录 Day37 完全背包理论基础 卡码网T52 LeetCode T518 零钱兑换II T377 组合总和IV
代码随想录 Day37 完全背包理论基础 卡码网T52 LeetCode T518 零钱兑换II T377 组合总和IV
58 0
|
6月前
|
缓存 算法 测试技术
【单调栈】【二分查找】LeetCode: 2454.下一个更大元素 IV
【单调栈】【二分查找】LeetCode: 2454.下一个更大元素 IV
|
6月前
leetcode-6111:螺旋矩阵 IV
leetcode-6111:螺旋矩阵 IV
44 0