188. Best Time to Buy and Sell Stock IV——LeetCode
2024-10-20 04:11:19
Say you have an array for which the ith 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.
题目大意:最多k次交易,问可以达到的最大获利。
思路:dp, 递推式:
dp[i, j] represents the max profit up until prices[j] using at most i transactions.
dp[i, j] = max(dp[i, j-1], prices[j] - prices[jj] + dp[i-1, jj]) { jj in range of [0, j-1] }
= max(dp[i, j-1], prices[j] + max(dp[i-1, jj] - prices[jj]))
dp[i, j] 表示最多i次交易时,价格为prices[j]时的最大获利。
核心代码如下:
int[][] dp = new int[k+1][n];
for (int i = 1; i <= k; i++) {
int localMax = dp[i-1][0] - prices[0];
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i][j-1], prices[j] + localMax);
localMax = Math.max(localMax, dp[i-1][j] - prices[j]);
}
}
最新文章
- GJM : Unity3D HIAR -【 快速入门 】 三、导入 SDK
- kangle 默认支持ETag,如果是用kangle做源不会识别,但是做cdn或反向代理会自动识别
- MyEclipse设置编码方式
- 图书馆管理系统SRS
- [JFinal 1] JFinal和SSH中使用拦截器的对比
- HDU 2852 KiKi&#39;s K-Number 树状数组 + 二分
- Sass&;Compass学习笔记(一)
- 解决ubuntu server mysql load data infile 导入本地文件ERROR 1148 (42000)错误。
- MVC5中使用Log4Net
- poj 2774 最长公共子串 后缀数组
- wget 常用参数释义
- Solr配置步骤
- 错误代码 0x800700b7 配置错误定义了重复的“system.web.extensions/scripting/scriptResourceHandler”节
- 前端:Jquery 处理同一Name的Radio组时,绑定checked属性异常的问题.(已解决)
- oracle-rman-2
- int 操作
- Perl、PHP、Python、Java 和 Ruby 比较【转载+整理】
- Windows 2012 R2 创建AD域
- 海思3518EV200 SDK中获取和保存H.264码流详解
- 1) Spring_HelloWorld
热门文章
- Linux之FTP篇
- java如何实现python的urllib.quote(str,safe=&#39;/&#39;)
- js event事件绑定的方法
- 表单提交前的confirm验证提示
- java使用netty的模型总结
- 如何将git上的代码迁移到Coding上
- 《Unity系列》Json文件格式的解析——初级教程
- artDialog组件应用学习(二)
- ArcGIS Enterprise 10.5.1 静默安装部署记录(Centos 7.2 minimal)- 5、安装Datastore
- 【Spring实战】—— 9 AOP环绕通知