只做瓶子包装设计的创意网站,什么叫高端网站定制,中信建设有限责任公司重庆沿江高速公路总承包部,传媒大学附近网站建设公司给你一个整数数组 prices 和一个整数 k #xff0c;其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说#xff0c;你最多可以买 k 次#xff0c;卖 k 次。
注意#xff1a;你不能同时参与多…给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 1
输入k 2, prices [2,4,1]
输出2
解释在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2 。
示例 2
输入k 2, prices [3,2,6,5,0,3]
输出7
解释在第 2 天 (股票价格 2) 的时候买入在第 3 天 (股票价格 6) 的时候卖出, 这笔交易所能获得利润 6-2 4 。随后在第 5 天 (股票价格 0) 的时候买入在第 6 天 (股票价格 3) 的时候卖出, 这笔交易所能获得利润 3-0 3 。 提示
1 k 1001 prices.length 10000 prices[i] 1000 采用动态规划dp[i][j]描述: 在第 i 天进行第 j 次交易。j是从0开始每次步长为2。因此j 为奇数表示买入j 为偶数表示卖出所能获得的最大利润。 初始化动态规划表格 j为奇数时dp[0][j]: 初始化为 -prices[0]。在第0天无论多少次买卖在买入时都是花费了prices[0]块钱。j为偶数时dp[0][j]初始化为0。在第0天利润一定是0。 遍历股票价格 遍历每一天模拟时间流逝。 更新动态规划表格 对于每一天 i 和每一种交易类型 j 如果 j 为奇数买入dp[i][j 1]: 在第 i 天买入股票的最大利润考虑前一天卖出股票而在当天买入股票的利润 dp[i-1][j]-prices[i]和前一天买入而当天无操作的较大值。如果 j 为偶数卖出dp[i][j 2]: 在第 i 天卖出股票的最大利润考虑前一天买入股票而当天卖出的利润 dp[i-1][j1]prices[i]和前一天已经卖出的较大值。 返回最大利润 返回动态规划表格的最后一个元素 dp[prices.size()-1][2*k]即在最后一天进行第 k 次交易所能获得的最大利润。 class Solution {
public:int maxProfit(int k, vectorint prices) {if(prices.size() 0) return 0;vectorvectorint dp(prices.size(),vectorint(2*k1,0));for(int j 1; j 2 * k; j 2){dp[0][j] -prices[0];}for(int i 1; i prices.size(); i ){for(int j 0; j 2 * k - 1; j 2){dp[i][j 1] max(dp[i-1][j1],dp[i-1][j] - prices[i]);dp[i][j 2] max(dp[i-1][j2],dp[i-1][j1] prices[i]);}}return dp[prices.size()-1][2*k];}
};
重点就在状态转移方程 dp[i][j 1] max(dp[i-1][j1],dp[i-1][j] - prices[i]);
表示在第 i 天进行第 j1 次交易买入的最大利润由以下两种情况决定
情况 1在前一天第 i-1 天进行第 j1 次交易买入。情况 2在前一天第 i-1 天进行第 j 次交易卖出然后在第 i 天进行第 j1 次交易买入。 dp[i][j 2] max(dp[i-1][j2],dp[i-1][j1] prices[i]);
表示在第 i 天进行第 j2 次交易卖出的最大利润由以下两种情况决定
情况 1在前一天第 i-1 天进行第 j2 次交易卖出。情况 2在前一天第 i-1 天进行第 j1 次交易买入然后在第 i 天进行第 j2 次交易卖出。
