建设网站模板下载,房地产网站建设方案,可以看封禁网站的浏览器,全能网站模板1买卖股票的最佳时机
给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔…1买卖股票的最佳时机
给定一个数组 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。提示
1 prices.length 1050 prices[i] 104
思路1暴力解法
暴力解法的思路是遍历所有可能的买入和卖出时机并计算它们之间的利润然后找出利润最大的情况。具体步骤如下 遍历所有可能的买入和卖出时机使用两重循环外层循环遍历可能的买入时机内层循环在外层循环中的每个买入时机后面遍历可能的卖出时机。 计算利润对于每一对买入和卖出时机计算卖出价格减去买入价格得到的利润。 找出最大利润在遍历过程中不断更新最大利润并记录对应的买入和卖出时机。 返回结果最终返回最大利润及对应的买入和卖出时机。
代码
class Solution {
public:// 计算股票的最大利润int maxProfit(vectorint prices) {int result 0; // 初始化最大利润为0for (int i 0; i prices.size(); i) { // 遍历所有可能的买入时机for (int j i 1; j prices.size(); j){ // 在每个买入时机后面遍历可能的卖出时机result max(result, prices[j] - prices[i]); // 计算当前买入和卖出时机的利润并更新最大利润}}return result; // 返回最大利润}
};
思路2
解题思路是基于动态规划的思想。首先我们定义了一个二维动态规划数组 dp其中 dp[i][0] 表示第 i 天不持有股票时的最大利润dp[i][1] 表示第 i 天持有股票时的最大利润。然后我们通过遍历股票价格列表在每一天都更新 dp 数组的值直到遍历完所有的天数。
在更新 dp 数组的过程中我们根据状态转移方程进行更新。对于第 i 天有两种情况
如果第 i 天不持有股票则其最大利润为前一天不持有股票的利润 dp[i-1][0]或者是前一天持有股票然后在第 i 天卖出股票得到的利润 dp[i-1][1] prices[i] 的较大值。如果第 i 天持有股票则其最大利润为前一天持有股票的利润 dp[i-1][1]或者是前一天不持有股票然后在第 i 天买入股票得到的利润 -prices[i] 的较大值。
根据以上思路我们在循环中更新 dp 数组的值最终返回最后一天不持有股票时的最大利润即 dp[len-1][0]。
注意这里说的是“持有”“持有”不代表就是当天“买入”也有可能是昨天就买入了今天保持持有的状态 dp数组如何初始化
由递推公式 dp[i][0] max(dp[i - 1][0], -prices[i]); 和 dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);可以看出
其基础都是要从dp[0][0]和dp[0][1]推导出来。
那么dp[0][0]表示第0天持有股票此时的持有股票就一定是买入股票了因为不可能有前一天推出来所以dp[0][0] - prices[0];
dp[0][1]表示第0天不持有股票不持有股票那么现金就是0所以dp[0][1] 0;
代码
class Solution {
public:// 计算股票的最大利润int maxProfit(vectorint prices) {int len prices.size(); // 获取股票价格列表的长度if (len 0) {return 0; // 如果列表为空返回0}vectorvectorint dp(len, vectorint(2)); // 定义二维动态规划数组dpfor (int i 0; i len; i) {// 根据状态转移方程填充dp数组if (i 0) {dp[i][0] 0;dp[i][1] -prices[i]; // 第一天持有股票的利润为 -prices[i]} else {// 不持有股票的利润为前一天不持有股票的利润与前一天持有股票今天卖出的利润的较大值dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]);// 持有股票的利润为前一天持有股票的利润与今天买入股票的利润的较大值dp[i][1] max(dp[i-1][1], -prices[i]); // -prices[i] 表示买入股票的利润}}return dp[len-1][0]; // 返回最后一天持有股票获得的利润}
};
2买卖股票的最佳时机 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 。 提示
1 prices.length 3 * 1040 prices[i] 104
思路
dp[i][0] 表示第i天持有股票所得现金。dp[i][1] 表示第i天不持有股票所得最多现金
重点 首先定义一个二维动态规划数组 dp其中 dp[i][0] 表示第 i 天不持有股票时的最大利润dp[i][1] 表示第 i 天持有股票时的最大利润。 初始条件设定为第一天即 dp[0][0] 表示第一天持有股票的利润为负的第一天股票价格dp[0][1] 表示第一天不持有股票的利润为0。 然后利用状态转移方程进行动态规划。遍历股票价格列表对于每一天的状态更新 dp 数组的值。 对于 dp[i][0]表示第 i 天不持有股票时的最大利润可以选择在前一天不持有股票的情况下保持不动或者在前一天持有股票的情况下在第 i 天卖出股票。因此取两者之间的较大值作为 dp[i][0] 的值。 对于 dp[i][1]表示第 i 天持有股票时的最大利润可以选择在前一天持有股票的情况下保持不动或者在前一天不持有股票的情况下在第 i 天买入股票。同样取两者之间的较大值作为 dp[i][1] 的值。 最终返回 dp[len - 1][1]表示最后一天不持有股票获得的最大利润即为问题的解。 dp[i - 1][0] 表示第 i - 1 天不持有股票时的最大利润即前一天的利润。dp[i - 1][1] - prices[i] 表示前一天持有股票时的最大利润减去第 i 天股票价格后的值即前一天持有股票然后在第 i 天卖出股票得到的利润。
因此max(dp[i - 1][0], dp[i - 1][1] - prices[i]) 取了这两者之间的较大值即在第 i 天不持有股票时我们要么保持不动要么前一天持有股票并在第 i 天卖出取两者利润的最大值。 dp[i - 1][1] 表示第 i - 1 天持有股票时的最大利润即前一天的利润。dp[i - 1][0] prices[i] 表示前一天不持有股票时的最大利润加上第 i 天股票价格后的值即前一天不持有股票然后在第 i 天买入股票得到的利润。
因此max(dp[i - 1][1], dp[i - 1][0] prices[i]) 取了这两者之间的较大值即在第 i 天持有股票时我们要么保持不动要么前一天不持有股票并在第 i 天买入取两者利润的最大值。
代码
class Solution {
public:// 计算股票的最大利润int maxProfit(vectorint prices) {int len prices.size(); // 获取股票价格列表的长度vectorvectorint dp(len, vectorint(2, 0)); // 定义二维动态规划数组dp初始化为0dp[0][0] - prices[0]; // 第一天持有股票的利润为 -prices[0]dp[0][1] 0; // 第一天不持有股票的利润为0for (int i 1; i len; i) {// 不持有股票的利润为前一天不持有股票的利润与前一天持有股票今天买入的利润的较大值dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和 买卖股票的最佳时机唯一不同的地方。// 持有股票的利润为前一天持有股票的利润与今天卖出股票的利润的较大值dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i]);}return dp[len - 1][1]; // 返回最后一天不持有股票获得的利润}
};
3买卖股票的最佳时机 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提示
1 prices.length 1050 prices[i] 105
3买卖股票的最佳时机 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提示
1 prices.length 1050 prices[i] 105
思路 定义动态规划数组 我们首先定义一个二维数组 dp其中 dp[i][j] 表示在第 i 天结束时进行第 j 次交易后的剩余最大现金。这里 j 取值范围为 0 到 4分别代表不进行交易、进行一次买入、进行一次卖出、进行两次买入、进行两次卖出。 初始化动态规划数组 对于第一天我们需要考虑可以进行的交易操作。因为题目要求最多可以完成两笔交易所以第一天可以进行第一次买入和第二次买入。因此我们将 dp[0][1] 和 dp[0][3] 设置为负的第一天股票价格表示在第一天结束时进行第一次买入和第二次买入操作后的剩余最大现金。 状态转移方程 接下来我们需要根据状态转移方程更新动态规划数组。具体地 对于进行买入操作的情况我们需要考虑前一天是否已经进行了相应的交易。根据状态转移方程我们取前一天结束时未进行买入操作和前一天结束时已经进行了买入操作但保持不变或者在当天买入的较大值。 对于进行卖出操作的情况同样需要考虑前一天是否已经进行了相应的交易。根据状态转移方程我们取前一天结束时未进行卖出操作和前一天结束时已经进行了卖出操作但保持不变或者在当天卖出的较大值。 返回结果 最后我们返回 dp[prices.size() - 1][4]表示第 len - 1 天结束时进行第二次卖出操作后的剩余最大现金即为问题的解。
代码
class Solution {
public:
int maxProfit(vectorint prices) {
if (prices.size() 0) return 0; // 如果股票价格列表为空则返回0
vectorvectorint dp(prices.size(), vectorint(5, 0)); // 定义二维动态规划数组dp行数为股票价格列表的长度列数为5初始化为0
dp[0][1] -prices[0]; // 第一天结束时进行第一次买入操作后的剩余最大现金为负的第一天股票价格
dp[0][3] -prices[0]; // 第一天结束时进行第二次买入操作后的剩余最大现金为负的第一天股票价格
for (int i 1; i prices.size(); i) {
// 计算第一次买入操作后的剩余最大现金
dp[i][0] dp[i - 1][0];
dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
// 计算第一次卖出操作后的剩余最大现金
dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]);
// 计算第二次买入操作后的剩余最大现金
dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
// 计算第二次卖出操作后的剩余最大现金
dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]);
}
return dp[prices.size() - 1][4]; // 返回第 len - 1 天结束时进行第二次卖出操作后的剩余最大现金
}
};
4买卖股票的最佳时机 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 。 提示
1 k 1001 prices.length 10000 prices[i] 1000
思路 边界情况处理 首先检查股票价格数组是否为空如果为空直接返回0。 初始化动态规划数组 dp 创建一个二维数组 dp大小为 prices.size() × (2 * k 1)表示在不同天数和不同交易次数下的最大利润。 第一天情况的初始化 针对每次交易的买入操作将 dp[0][j]奇数索引设为 -prices[0]表示第一次买入的情况。 动态规划状态转移 从第二天开始遍历股票价格数组。对于每天和每种交易次数根据状态转移方程更新 dp[i][j] dp[i][j 1]表示第 j/2 1 次买入股票的最大利润可以选择继续保持不持有或者在前一天持有的基础上卖出。dp[i][j 2]表示第 j/2 1 次卖出股票的最大利润可以选择继续持有或者在前一天未持有的基础上买入。 返回结果 在所有交易完成后即遍历完所有天数返回 dp[prices.size() - 1][2 * k]表示在最后一天结束时最多进行 k 次交易的最大利润。
代码
class Solution {
public:int maxProfit(int k, vectorint prices) {// 边界情况处理如果股票价格数组为空直接返回0if (prices.size() 0) return 0;// 初始化动态规划数组vectorvectorint dp(prices.size(), vectorint(2 * k 1, 0));// 初始化第一天的情况for (int j 1; j 2 * k; j 2) {dp[0][j] -prices[0]; // 第一次买入的情况}// 动态规划根据状态转移方程更新dp数组for (int i 1; i prices.size(); i) {for (int j 0; j 2 * k - 1; j 2) {// 第i天未持有股票的情况考虑继续未持有或者在前一天持有的基础上卖出dp[i][j 1] max(dp[i - 1][j 1], dp[i - 1][j] - prices[i]);// 第i天持有股票的情况考虑继续持有或者在前一天未持有的基础上买入dp[i][j 2] max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i]);}}// 返回最后一天结束时最多进行k次交易的最大利润return dp[prices.size() - 1][2 * k];}
};
