题解 | #买卖股票的最好时机(三)#
买卖股票的最好时机(三)
https://www.nowcoder.com/practice/2fea2b0349df4f7689f6f5a882e4f129
#include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { int k; scanf("%d", &k); vector<int> prices(k); int a; for(int i = 0; i < k; ++i) { scanf("%d", &a); prices[i] = a; } int max_num = 2; vector<vector<vector<int>>> dp(k, vector<vector<int>>(max_num + 1, vector<int>(2))); //使用动态规划数组dp,该数组代表第i天,最大允许交易次数为j次时,未持股(第三维为0)或持股(第三维为1)时利润最大值 for(int i = 0; i < k; ++i) //初始值,当允许交易次数为0时的初始化 { dp[i][0][0] = 0; //不允许交易且不持股,最大利润为0 dp[i][0][1] = -prices[i]; //不允许交易且持股,只能亏钱 } for(int i = 1; i <= max_num; ++i) //初始值,对第一天各种情况的初始化 { dp[0][i][0] = 0; dp[0][i][1] = -prices[0]; } for(int i = 1; i < k; ++i) { for(int j = 1; j <= max_num; ++j) { dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]); dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]); //每次买入为交易的开始 } } if(dp[k - 1][max_num][0] > 0) printf("%d", dp[k - 1][max_num][0]); else printf ("%d", 0); return 0; } // 64 位输出请用 printf("%llcstdiod")