一、121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
思路：只能买一次，从前往后依次找到当前的最低价，然后用当前价格减去之前遇到的最低价，所得的最大值就是最大利润。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int zuidiprice = prices[0], maxLirun = 0, len = prices.size();
for (int i = 1; i < len; ++i) {
maxLirun = std::max(maxLirun, prices[i] - zuidiprice);
zuidiprice = std::min(prices[i], zuidiprice);
}
return maxLirun;
}
};
二、122. 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
思路：可以买卖无限次，每天都有两种状态，要么是今天手里有股票，要么是今天手里没有股票。今天手里有股票来自于昨天就有或者昨天没有今天买的，今天手里没有股票来自于昨天就没有或者昨天有今天卖的。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int yesterdayhave = -prices[0], yesterdaydayno = 0;
for (int i = 1; i < prices.size(); ++i) {
int jintianhave = std::max(yesterdayhave, yesterdaydayno - prices[i]);
int jintianno = std::max(yesterdaydayno, yesterdayhave + prices[i]);
yesterdayhave = jintianhave;
yesterdaydayno = jintianno;
}
return yesterdaydayno;
}
};
三、123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
思路：每天有五种状态，分别是今天是买了一次，卖了一次，买了两次，卖了两次，还有一种状态是一次都没买过这种状态的利润是0，所以不用计算。
买了一次，就取当前买的最低价。
卖了一次，取卖了一次的最高利润和今天卖出的最大值。
买了两次，取买了两次的最大值和今天买入的最大值。
卖了两次，取卖了两次的最大值和今天卖出的最大值。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
int buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], sell2 = 0;
for (int i = 1; i < len; ++i)
{
buy2 = max(buy2, sell1 - prices[i]);
sell2 = max(sell2, buy2 + prices[i]);
sell1 = max(sell1, buy1 + prices[i]);
buy1 = max(buy1, -prices[i]);
}
return sell2;
}
};
四、188. 买卖股票的最佳时机 IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
思路：有了上一题最多买卖两次的思路，就知道买N次等于已经买N次和卖了N-1次今天再买的最大值。卖N次等于当前就卖了N次和买了N次今天卖了的最大值。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (k <= 0 || prices.size() < 2) return 0;
vector<vector<int>> dp(k, vector<int>(2));
for (int i = 0; i < k; ++i)
dp[i][0] = -prices[0];
int len = prices.size();
for (int i = 1; i < len; ++i) {
for (int j = 1; j < k; ++j) {
dp[j][1] = max(dp[j][1], dp[j][0] + prices[i]);
dp[j][0] = max(dp[j][0], dp[j - 1][1] - prices[i]);
}
dp[0][1] = max(dp[0][1], dp[0][0] + prices[i]);
dp[0][0] = max(dp[0][0], -prices[i]);
}
return dp[k - 1][1];
}
};
五、714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
思路：可以买卖无限次，每天都有两种状态，要么是今天手里有股票，要么是今天手里没有股票。今天手里有股票来自于昨天就有或者昨天没有今天买的，今天手里没有股票来自于昨天就没有或者昨天有今天卖的。卖的计算时把手续费减去即可。
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int yesterdayhave = -prices[0], yesterdaydayno = 0;
for (int i = 1; i < prices.size(); ++i) {
int jintianhave = std::max(yesterdayhave, yesterdaydayno - prices[i]);
int jintianno = std::max(yesterdaydayno, yesterdayhave + prices[i] - fee);
yesterdayhave = jintianhave;
yesterdaydayno = jintianno;
}
return yesterdaydayno;
}
};
六、309. 买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
思路：每一天都依赖前天和昨天的状态。今天没有：昨天就没有，或者昨天有今天卖了。今天有：昨天就有，前天没有今天买了。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1) return 0;
if (prices.size() == 2) if (prices[0] < prices[1]) return prices[1] - prices[0]; else return 0;
vector<int> dp_qiantian(2), dp_zuotian(2), dp_jintian(2);
dp_qiantian[1] = -prices[0];//初始化第一天有
dp_zuotian[0] = std::max(prices[1] - prices[0], 0);//初始化第二天没有
dp_zuotian[1] = std::max(-prices[0] , -prices[1]);//初始化第二天有
for (int i = 2; i < prices.size(); ++i) {
//今天没有：昨天就没有，或者昨天有今天卖了
dp_jintian[0] = std::max(dp_zuotian[0], dp_zuotian[1] + prices[i]);
//今天有：昨天就有，前天没有今天买了
dp_jintian[1] = std::max(dp_zuotian[1], dp_qiantian[0] - prices[i]);
dp_qiantian = dp_zuotian;
dp_zuotian = dp_jintian;
}
return dp_jintian[0];
}
};