【刷题-LeetCode】188 Best Time to Buy and Sell Stock IV
- 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 = 2
Output: 2
Explanation: 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 = 2
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.
解 动态规划
用一个二维矩阵trans,矩阵的列表示交易的价格,矩阵的行表示交易的次数,矩阵的值表示当前能够获得的最大利润
以允许3交易为例,考察第3天的最大利润trans[3][3]
- 第3天什么都不做,\(trans[3][3] = trans[3][2]\)
- 以第1天价格买入,第3天价格卖出,\(trans[3][3]=prices[3]-prices[1] + trans[2][1]\)
- 以第2天价格买入,第3天价格卖出,\(trans[3][3]=prices[3]-prices[2] + trans[2][2]\)
取最大值即为结果。实现如下:
用两个数组buy和sell来分别表示第i次买入交易的最大收益值和第i次卖出交易的最大收益值
1.第i次买操作买下当前股票之后剩下的最大利润为第(i-1)次卖掉股票之后的利润-当前的股票价格.状态转移方程为:
buy[i] = max(sell[i-1]- curPrice, buy[i]);
2.第i次卖操作卖掉当前股票之后剩下的最大利润为第i次买操作之后剩下的利润+当前股票价格.状态转移方程为:
sell[i] = max(buy[i]+curPrice, sell[i]);
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size() ==0) return 0;
int len = prices.size(), ans =0;
if(k >= len/2){
for(int i = 1; i < len; i++)
if(prices[i]-prices[i-1]>0)ans += prices[i]-prices[i-1];
return ans;
}
vector<int> buy(len+1, INT_MIN), sell(len+1, 0);
for(auto val: prices)
{
for(int i =1; i <= k; i++)
{
buy[i] = max(sell[i-1]-val, buy[i]);
sell[i] = max(buy[i]+val, sell[i]);
}
}
return sell[k];
}
};
Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock III
[Best Time to Buy and Sell Stock IV](
最新文章
- iOS 开发 -----公司测试打包上传流程
- Windows 10下通过蓝牙连接iPhone个人热点进行共享上网
- js中eval() 方法的使用以及一些特殊的使用方式
- TCP链接时主动close时可能的rst报文
- [游戏模版6] Win32 graph
- play framework 框架安装及myeclipse 导入项目
- 坚持自学的第二天,bootstrap初入门
- Spring Cloud Eureka Server例子程序
- ubuntu下eclipse突然崩溃,解决办法
- .NET 4.0里异常处理的新机制
- seajs源码阅读
- unity slua整合帅气的lua-pb解析protobuf
- java 入门之八大内置基本类型
- 分布式:2PC,3PC,Paxos,Raft,ISR [转]
- (七十三)iOS本地推送通知的实现
- springboot+VUE(一)
- ELK收集日志到mysql
- 数论细节梳理&;模板
- oracle 视图带参数
- HTML5实现简单圆周运动示例
热门文章
- Android4.4开机动画播放视频
- JavaScript 中的防抖和节流
- SpringBoot整合openoffice实现word文档的读取和导入及报错处理
- LocalDateTime与Date相互转换
- java.lang.StackOverflowError报错
- windows串口之虚拟串口和Access port
- Codeforces 1076G Array Game 题解
- OverFeat:Integrated Recognition, Localization and Detection using Convolutional Networks
- Improving Adversarial Robustness via Channel-Wise Activation Suppressing
- Geometric GAN