<leetcode c++>卖股票系列
2021-02-16 06:18
阅读：463
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
int maxProfit(vectorint>& prices) { int n=prices.size(); if(n1)return 0; int min_p=prices[0]; int max_p=0; for(int i=1;i) { min_p=min(min_p,prices[i]); max_p=max(max_p,prices[i]-min_p); } return max_p; }
122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
int maxProfit(vectorint>& prices) { int n=prices.size(); if(n==0)return 0; int dp_i_0=0; int dp_i_1=-prices[0]; for(int i=1;i){ dp_i_0=max(dp_i_0,dp_i_1+prices[i]); dp_i_1=max(dp_i_1,dp_i_0-prices[i]); } return max(dp_i_0,0); }
123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
int maxProfit(vectorint>& prices) { int n=prices.size(); if(n==0)return 0; vectorint>>> dp(n+1,vector int>>(3,vectorint>(2,0)));//dp[i][k][0 or 1] 前i-1个元素，进行了k次交易，当前有无持有 dp[0][1][1]=-1e8; dp[0][2][1]=-1e8; for(int i=1;i){ for(int k=1;k3;k++){ dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i-1]); dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i-1]); } } return max(dp[n][1][0],dp[n][2][0]); }
188. 买卖股票的最佳时机 IV
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
int maxP(vectorint>& prices) { int n=prices.size(); if(n==0)return 0; int dp_i_0=0; int dp_i_1=-prices[0]; for(int i=1;i){ dp_i_0=max(dp_i_0,dp_i_1+prices[i]); dp_i_1=max(dp_i_1,dp_i_0-prices[i]); } return max(dp_i_0,0); } int maxProfit(int max_k, vectorint>& prices) { int n=prices.size(); if(n==0)return 0; if(max_k>prices.size()/2)return maxP(prices); vector int>>> dp(n+1,vector int>>(max_k+1,vectorint>(2,0)));//dp[i][k][0 or 1] 前i-1个元素，进行了k次交易，当前有无持有 for(int i=1;i){ dp[0][i][1]=-1e8; } //for(int ) for(int i=1;i){ for(int k=1;k){ dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i-1]); dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i-1]); } } return dp[n][max_k][0]; }
309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。?
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
int maxProfit(vectorint>& prices) { int n=prices.size(); if(n==0)return 0; //vector> dp(n,vector int dp_i_0=0;//冷冻 int dp_i_1=-prices[0];//买入 int dp_pre_0=0; for(int i=1;i(3,INT_MIN)); ){ int tmp=dp_i_0; dp_i_0=max(dp_i_0,dp_i_1+prices[i]); dp_i_1=max(dp_i_1,dp_pre_0-prices[i]); dp_pre_0=tmp; } return dp_i_0; }
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：<leetcode c++>卖股票系列
文章链接：http://soscw.com/index.php/essay/55966.html
文章标题：<leetcode c++>卖股票系列
文章链接：http://soscw.com/index.php/essay/55966.html
评论
亲，登录后才可以留言！