动态规划之买卖股票的最佳时机——Leecode
1.题目：买卖股票的最佳时机
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/description/
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
代码实现：
//方法一
class Solution {
public:
int maxProfit(vector<int>& prices) {
int b1=INT_MIN;
int s1=0;
for(int i=0;i<prices.size();i++)
{
b1=max(b1,-prices[i]);
s1=max(s1,b1+prices[i]);
}
return s1;
}
};
//方法二
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size()<1)
return 0;
int res=0;
int m = prices[0];//买入最小值
for(int i=1;i<prices.size();i++)
{
res=max(res,prices[i]-m);
m=min(prices[i],m);
}
return res;
}
};
2.题目 ：买卖股票的最佳时机 II
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/description/
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 =3 。
示例 2:
输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
原理：
只要把所有的连续上升子串的的两个端点找到就好了
代码实现：
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()) //判断输入是否为空
return 0;
//贪心算法
int maxPro = 0,temp = 0;//最大收益、差值
for(int i=1;i<prices.size();i++)//判断所有上升的值
{
temp = prices[i]-prices[i-1];
if(temp>0)
maxPro +=temp;
}
return maxPro;
}
};
3.题目：买卖股票的最佳时机 III
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/description/
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1] 输出: 0 解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
原理：
确保每次剩下的钱最多
7 1 5 3 6 4 第一次买入 -7 -1 -1 -1 -1 -1 第一次卖出 0 0 4 4 5 5 第二次买入 -7 -1 -1 1 1 1 第二次卖出 0 0 4 4 7 7
3 3 5 0 0 3 1 4 第一次买入 -3 -3 -3 0 0 0 0 0 第一次卖出 0 0 2 2 2 3 3 4 第二次买入 -3 -3 -3 2 2 2 2 2 第二次卖出 0 0 2 2 2 5 5 6
代码实现：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int b1=INT_MIN,b2=INT_MIN;//买入的初始值为int的下界，-2^31-1
int s1=0,s2=0; //卖出初始化为0
for(int i=0;i<prices.size();i++)
{
b1=max(b1,-prices[i]);
s1=max(s1,b1+prices[i]);
b2=max(b2,s1-prices[i]);
s2=max(s2,b2+prices[i]);
}
return s2;
}
};
题目4：买卖股票的最佳时机 IV
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/description/
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2 输出: 2 解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2 输出: 7 解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0=3 。
原理：
注意：当交易次数大于天数，看作是贪心算法
代码实现：
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(k > prices.size())//当交易次数大于天数，看作是贪心算法
{
int res = 0;
for(int i = 1 ; i < prices.size(); i++) if(prices[i] > prices[i-1]) res += prices[i]-prices[i-1];
return res;
}
vector<int> sell(k+1, 0), buy(k+1, INT_MIN);//第n次的卖出、买入的数组
for(int i = 0; i < prices.size() ; i++)
{
for(int j = k; j > 0 ; j--) //交易次数,从后面倒过来
{
sell[j] = max(sell[j], buy[j] + prices[i]);
buy[j] = max(buy[j], sell[j-1] - prices[i]);
}
}
return sell[k];
}
};
更多精彩内容
