121. 买卖股票的最佳时机——允许完成一次交易

题目描述

给定一个数组，它的第 $i$ 个元素是一支给定股票第 $i$ 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

题目分析

一次遍历寻找当前遍历过的数据的最小值，如果当前遍历到的数据不是当前遍历过的数据的最小值，那么就计算当前可以获得的最大利润。

code

class Solution {
public:int maxProfit(vector<int>& prices){int i,ans=0,minn;if(prices.empty()) return 0;  //力扣的空数组奇葩数据minn=prices[0];  //初始化for(i=1;i<prices.size();i++){//一次遍历if(prices[i]<minn)//判断当前遍历到的数据是否为当前遍历过的数据的最小值minn=prices[i];else//否则计算当前可以获得的最大利润ans=max(ans,prices[i]-minn);}return ans;//输出}
};

122. 买卖股票的最佳时机 II——允许多次交易

题目描述

给定一个数组，它的第 $i$ 个元素是一支给定股票第 $i$ 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
提示：
$1\le prices.length\le 3\times 10^4$
$0\le prices[i]\le 10^4$

题目分析

因为可以尽可能地完成更多的交易，可以多次买卖一支股票，那么说明可以用贪心。
我们逢低便买入，逢高便卖出。
只要前一天的价格小于后一天的价格便在前一天买入后一天卖出。

code

class Solution {
public:int maxProfit(vector<int>& prices){if(prices.size()<=1) return 0;int i,ans=0;for(i=1;i<prices.size();i++){//贪心ans+=max(prices[i]-prices[i-1],0);}return ans;}
};

123. 买卖股票的最佳时机 III——允许完成两次交易

题目描述

给定一个数组，它的第 $i$ 个元素是一支给定的股票在第 $i$ 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

题目分析

一道 $dp$ 题，初始化后用 $f[1]$ 存储第一次买入后可以获得的最大值，用 $f[2]$ 存储第一次买出后可以获得的最大值，用 $f[3]$ 存储第二次买入后可以获得的最大值，用 $f[4]$ 存储第二次买出后可以获得的最大值。
易得$dp$ 方程式为·：
$f[1]=max(f[1],f[0]-prices[i])$
$f[2]=max(f[2],f[1]+prices[i])$
$f[3]=max(f[3],f[2]-prices[i])$
$f[4]=max(f[4],f[3]+prices[i])$

code

class Solution {
public:int maxProfit(vector<int>& prices){if(prices.empty()) return 0;int n=prices.size();int m=max(n+1,5);int i,f[m];f[0]=0;f[1]=-prices[0];f[2]=INT_MIN;f[3]=INT_MIN;f[4]=INT_MIN;for(i=0;i<n;i++){f[1]=max(f[1],f[0]-prices[i]);f[2]=max(f[2],f[1]+prices[i]);f[3]=max(f[3],f[2]-prices[i]);f[4]=max(f[4],f[3]+prices[i]);}return f[4];}
};

188. 买卖股票的最佳时机 IV——允许完成 $k$ 次交易

题目描述

给定一个整数数组 $prices$ ，它的第 $i$ 个元素 $prices[i]$ 是一支给定的股票在第 $i$ 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 $k$ 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

题目分析

思路与上题一致，但需要判断当 $k>=n/2$ 时的情况。
当 $k>=n/2$ 时，退化为不限制交易次数。

code

class Solution {
public:int maxProfit(int k ,vector<int>& prices){if(prices.empty()) return 0;int n=prices.size();int i,j;if(k>=n/2){int ans=0;for(i=1;i<n;i++)if(prices[i]>prices[i-1])ans+=prices[i]-prices[i-1];return ans;}int m=max(n+1,k*2+1);int f[m+1];memset(f,0x80,sizeof(f));f[0]=0;f[1]=-prices[0];for(i=0;i<n;i++){for(j=1;j<=k*2;j++){if(j%2==1)  f[j]=max(f[j],f[j-1]-prices[i]);else f[j]=max(f[j],f[j-1]+prices[i]);}}return f[k*2];}
};

309. 最佳买卖股票时机含冷冻期——允许多次交易并含冷冻期

题目描述

给定一个整数数组，其中第 $i$ 个元素代表了第 $i$ 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 $1$ 天)。

题目分析

设我们目前持有一支股票，对应的累计最大收益记为 $f[i][0]$；
我们目前不持有任何股票，并且处于冷冻期中，对应的累计最大收益记为 $f[i][1]$；
我们目前不持有任何股票，并且不处于冷冻期中，对应的累计最大收益记为 $f[i][2]$。
则易推得 $dp$ 方程式。
然后再滚动一下就好了（虽然也没省多少空间）

code

class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.empty()) return 0;int n=prices.size();int f[3],x,y,z,i;memset(f,0,sizeof(f));f[0]=-prices[0];for(i=0;i<n;i++){x=f[0];y=f[1];z=f[2];f[0]=max(x,z-prices[i]);f[1]=x+prices[i];f[2]=max(y,z);}return max(f[1],f[2]);}
};

714. 买卖股票的最佳时机含手续费——允许多次交易并含手续费

题目描述

给定一个整数数组 $prices$，其中第 $i$ 个元素代表了第 $i$ 天的股票价格 ；非负整数 $fee$ 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

题目分析

显然是 $P2+P4$,直接放代码吧。

code

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {if(prices.empty()) return 0;int n=prices.size();int i,x=0,y=-prices[0];for(i=0;i<n;i++){x=max(x,y+prices[i]-fee);y=max(y,x-prices[i]);}return max(x,y);}
};