问题描述:
给定一个整数数组prices,它的第i个元素prices[i]是一支给定的股票在第i天的价格,设计一个算法来计算你所能获取的最大利润。
算法思路:
动态规划
C++源码:
class Solution {
public:
//1.最多交易一次
int maxProfit(vector<int>& prices) {
int maxPro = 0; //最大收益
int buyPri = INT_MAX; //当前买入价格
for (int i = 0; i < prices.size(); i++) {
if (prices[i] - buyPri < 0) {
buyPri = prices[i];
} else if (prices[i] - buyPri > maxPro) {
maxPro = prices[i] - buyPri;
}
}
return maxPro;
}
int maxProfit(vector<int>& prices) {
if (prices.size() < 2) {
return 0;
}
int buy = -prices[0]; //买入状态最大收益
int self = 0; //卖出状态最大收益
for (int i = 1; i < prices.size(); i++) {
self = max(self, buy + prices[i]);
buy = max(buy, -prices[i]);
}
return self;
}
//2.不限交易次数
int maxProfit(vector<int>& prices) {
int maxPro = 0; //累计收益
int buyPri = -1; //当前买入价格,-1表示未持有
for (int i = 1; i < prices.size(); i++) {
if (buyPri < 0 && prices[i] > prices[i - 1]) {
buyPri = prices[i - 1];
} else if (buyPri >= 0 && prices[i] < prices[i - 1]) {
maxPro += prices[i - 1] - buyPri;
buyPri = -1;
}
}
if (buyPri >= 0) {
maxPro += prices.back() - buyPri;
}
return maxPro;
}
int maxProfit(vector<int>& prices) {
if (prices.size() < 2) {
return 0;
}
int buy = -prices[0]; //买入状态最大收益
int self = 0; //卖出状态最大收益
for (int i = 1; i < prices.size(); i++) {
int buy_old = buy;
buy = max(buy, self - prices[i]);
self = max(self, buy_old + prices[i]);
}
return self;
}
//3.最多交易2次
int maxProfit(vector<int>& prices) {
if (prices.size() < 2) {
return 0;
}
int first_buy = -prices[0]; //第一次买入状态最大利润
int first_self = 0; //第一次卖出状态最大利润
int second_buy = -prices[0]; //第二次买入状态最大利润
int second_self = 0; //第二次卖出状态最大利润
for (int i = 1; i < prices.size(); i++) {
second_self = max(second_self, second_buy + prices[i]);
second_buy = max(second_buy, first_self - prices[i]);
first_self = max(first_self, first_buy + prices[i]);
first_buy = max(first_buy, -prices[i]);
}
return second_self;
}
//4.最多交易k次
int maxProfit(int k, vector<int>& prices) {
if (k < 1 || prices.size() < 2) {
return 0;
}
vector<int> buy(k, -prices[0]); //buy[i]表示第i次买入状态最大利润(i=0表示首次)
vector<int> self(k, 0); //self[i]表示第i次卖出状态最大利润
for (int i = 1; i < prices.size(); i++) {
buy[0] = max(buy[0], -prices[i]);
self[0] = max(self[0], buy[0] + prices[i]);
for (int j = 1; j < k; j++) {
int temp = buy[j];
buy[j] = max(buy[j], self[j - 1] - prices[i]);
self[j] = max(self[j], temp + prices[i]);
}
}
return self.back();
}
//6.不限交易次数,每次交易收取手续费
int maxProfit(vector<int>& prices, int fee) {
if (prices.size() < 2) {
return 0;
}
int buy = -prices[0]; //当前买入状态最大利润
int self = 0; //当前卖出状态最大利润
for (int i = 1; i < prices.size(); i++) {
buy = max(buy, self - prices[i]);
self = max(self, buy + prices[i] - fee);
}
return self;
}
};
//5.不限交易次数,卖出后第二天不能买入
int maxProfit(vector<int>& prices) {
if (prices.size() < 2) {
return 0;
}
int buy = -prices[0]; //当前买入状态的最大利润
int self_freez = 0; //当前卖出且冻结状态的最大利润
int self_free = 0; //当前卖出且非冻结状态的最大利润
for (int i = 1; i < prices.size(); i++) {
int self_free_old = self_free;
self_free = max(self_free, self_freez);
self_freez = buy + prices[i];
buy = max(buy, self_free_old - prices[i]);
}
return max(self_freez, self_free);
}