首页 > 代码库 > 188. Best Time to Buy and Sell Stock IV leetcode解题笔记
188. Best Time to Buy and Sell Stock IV leetcode解题笔记
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).
这一题比上一题出现的变化 为 限制不再为两次 而是K次 再一次增加了难度
因为上一题的原因 这里想到了常用的一种算法 动态规划 虽然上一题的动态规划很抽象 但是这里我们具体化一点
首先我们的动态方程怎么设计 根据要求
能不能用一个二维数组profit[i,t]表示 通过T次交易 在第I个商品能获得的最大利润 那么profit[n,k]就是在第N个商品通过K次交易能获得的最大利润
根据推理 得出下列方程
profit[i,t]=max(profit(i-1,t),prices[i]+tmp)
tmp=max(tmp,profit(i-1,j-1)-prices[i])
tmp初始化为第一个商品的价格
这里解释一下 tmp的方程怎么来的 profit(i-1,j-1)-prices[i]表明 在第i-1个商品通过j-1次交易获得利润后 再买入第i个商品 并且跟之前的tmp比较取最大值
profit[i,t]中prices[i]+tmp 表明在之前的tmp基础上 卖出第I个商品获得的利润 和除去第I个商品获得的利润作比较 最大值
同时我们要知道K次是用户自定的 这里有一种特殊情况 我们买东西和卖东西就是两次动作 假设数组有四个数 我们最多进行两次交易 也就是4/2 假设用户给定K大于4/2 就回到了之前我们解决的第二个问题 不限定交易次数 获得最大交易值
这种特殊情况显然不能用动态方程 先除去这种情况 再用动态方程求解
有了思路 开始码代码
public class Solution {
public int maxProfit(int k, int[] prices) {
if(k>prices.length/2)
return inmaxProfit(prices);
int profit[][] =new int[k+1][prices.length];
for(int i=1;i<=k;i++){
int tmp=-prices[0];
for(int j=1;j<prices.length;j++){
profit[i][j]=Math.max(profit[i][j-1],prices[j]+tmp);
tmp=Math.max(tmp,profit[i-1][j-1]-prices[j]);
}
}
return profit[k][prices.length-1];
}
public int inmaxProfit(int[] prices){
int profit=0;
for(int i=0;i<prices.length-1;i++){
int diff=prices[i+1]-prices[i];
if(diff>0){
profit++;
}
}
return profit;
}
}
提交
看看哪里出了问题
给出的K是2 大于三个数的一半 所以进入的是第二个函数
profit++ 错了 应该是profit+=diff 修改 提交
public class Solution {
public int maxProfit(int k, int[] prices) {
if(k>prices.length/2)
return inmaxProfit(prices);
int profit[][]=new int[k+1][prices.length];
for(int i=1;i<=k;i++){
int tmp=-prices[0];
for(int j=1;j<prices.length;j++){
profit[i][j]=Math.max(profit[i][j-1],prices[j]+tmp);
tmp=Math.max(tmp,profit[i-1][j-1]-prices[j]);
}
}
return profit[k][prices.length-1];
}
public int inmaxProfit(int[] prices){
int profit=0;
for(int i=0;i<prices.length-1;i++){
int diff=prices[i+1]-prices[i];
if(diff>0){
profit+=diff;
}
}
return profit;
}
}
成功
188. Best Time to Buy and Sell Stock IV leetcode解题笔记