本文主要是介绍Day43- 动态规划part11，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、买卖股票的最佳时机
题目一：买卖股票的最佳时机 III
123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
/** @lc app=leetcode.cn id=123 lang=cpp** [123] 买卖股票的最佳时机 III*/// @lc code=start
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int buy1 = -prices[0], sell1 = 0;int buy2 = -prices[0], sell2 = 0;for (int i = 1; i < n; ++i) {buy1 = max(buy1, -prices[i]);sell1 = max(sell1, buy1 + prices[i]);buy2 = max(buy2, sell1 - prices[i]);sell2 = max(sell2, buy2 + prices[i]);}return sell2;}
};
// @lc code=end题目二：买卖股票的最佳时机 IV
188. 买卖股票的最佳时机 IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
class Solution {
public:int maxProfit(int k, vector<int>& prices) {if (prices.empty()) {return 0;}int n = prices.size();k = min(k, n / 2);vector<vector<int>> buy(n, vector<int>(k + 1));vector<vector<int>> sell(n, vector<int>(k + 1));buy[0][0] = -prices[0];sell[0][0] = 0;for (int i = 1; i <= k; ++i) {buy[0][i] = sell[0][i] = INT_MIN / 2;}for (int i = 1; i < n; ++i) {buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i]);for (int j = 1; j <= k; ++j) {buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]); }}return *max_element(sell[n - 1].begin(), sell[n - 1].end());}
};这篇关于Day43- 动态规划part11的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
