2018钓鱼网站建设,论网站建设技术的作者是谁,厦门关键词优化服务,seo企业顾问目录
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
123. 买卖股票的最佳时机 III
188. 买卖股票的最佳时机 IV 121. 买卖股票的最佳时机
题目描述#xff1a; 给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只…目录
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
123. 买卖股票的最佳时机 III
188. 买卖股票的最佳时机 IV 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。提示
1 prices.length 1050 prices[i] 104
实现代码与解析
遍历
class Solution {
public:int maxProfit(vectorint prices) {int low INT_MAX;int res 0;for (int i 0; i prices.size(); i){low min(low, prices[i]);res max(res, prices[i] - low);}return res;}
};
原理思路 简单题就是遍历找前后最大差值而已。 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 。提示
1 prices.length 3 * 1040 prices[i] 104
实现代码与解析
贪心
class Solution {
public:int maxProfit(vectorint prices) {int result0;for(int i1;iprices.size();i){//赚钱直接卖出if(prices[i]-prices[i-1]0) resultresultprices[i]-prices[i-1];}return result;}
};
原理思路 只要赚钱就卖出。 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提示
1 prices.length 1050 prices[i] 105
实现代码与解析
动态规划 class Solution {
public:int maxProfit(vectorint prices) {// int f[prices.size()][5]vectorvectorint f(prices.size(), vectorint(5, 0));f[0][0] 0, f[0][1] -prices[0], f[0][2] 0, f[0][3] -prices[0], f[0][4] 0; // 未持有、第一次持有股票第一次不持有股票 第二次持有股票第二次不持有股票的金额for (int i 1; i prices.size(); i){f[i][1] max(f[i - 1][1], f[i - 1][0] - prices[i]); // 第i天第一次持有状态的最大金额 max(已经持有第i天购入) f[i][2] max(f[i - 1][2], f[i - 1][1] prices[i]); // 第i天第一次不持有状态的最大金额 max(已经不持有 第 i 天卖出)f[i][3] max(f[i - 1][3], f[i - 1][2] - prices[i]); // 第i天第二次持有状态最大金额 max(已经第二次持有 第 i 天购入)f[i][4] max(f[i - 1][4], f[i - 1][3] prices[i]); // 第i天第二次不持有状态最大金额 max(已经第二次不持有 第i天卖出)}return f[prices.size() - 1][4]; // 根据dp数组的含义最后一天后不持有的最大金额为结果}
}
原理思路 根据题意每天可以有四个状态第一次持有股票第一次不持有股票 第二次持有股票第二次不持有股票所以可以定义出dp数组表示第 i 天四个状态的最大金额。当然还有一次没买入的状态也就是下标0的位置本身就都为0就不再过程中单独赋值了 初始化可以理解为在当天买入又在当天卖出所以第一次买入和第二次买入利润为负数不要奇怪负数的理解就是当前不赚还亏钱这点很重要帮助我们理解dp数组。所以根据dp数组含义不难写出递推公式。
递推公式 f[i][1] max(f[i - 1][1], f[i - 1][0] - prices[i]); // 第i天第一次持有状态的最大金额 max(已经第一次持有第 i 天购入) f[i][2] max(f[i - 1][2], f[i - 1][1] prices[i]); // 第i天第一次不持有状态的最大金额 max(已经第一次不持有 第 i 天卖出) f[i][3] max(f[i - 1][3], f[i - 1][2] - prices[i]); // 第i天第二次持有状态最大金额 max(已经第二次持有 第 i 天购入) f[i][4] max(f[i - 1][4], f[i - 1][3] prices[i]); // 第i天第二次不持有状态最大金额 max(已经第二次不持有 第 i 天卖出) 最后输出结果即可当然可以看出状态只由上一层中左上和上状态计算得到所以可以一维优化。 为什么都取max? 买入时取max说明买入花的钱越少剩的钱越多。 卖出时取max说明卖出的利润多赚的钱越多。
注意点买入为减卖出为加。
一维优化
class Solution {
public:int maxProfit(vectorint prices) {// int f[prices.size()][5]vectorint f(5, 0);f[0] 0, f[1] -prices[0], f[2] 0, f[3] -prices[0], f[4] 0; // 第一次持有股票第一次不持有股票 第二次持有股票第二次不持有股票的金额for (int i 1; i prices.size(); i){f[1] max(f[1], f[0] - prices[i]); // 第i天第一次持有状态的最大金额 max(已经持有第i天购入) f[2] max(f[2], f[1] prices[i]); // 第i天第一次不持有状态的最大金额 max(已经不持有 第 i 天卖出)f[3] max(f[3], f[2] - prices[i]); // 第i天第二次持有状态最大金额 max(已经第二次持有 第 i 天购入)f[4] max(f[4], f[3] prices[i]); // 第i天第二次不持有状态最大金额 max(已经第二次不持有 第i天卖出)}return f[4]; // 根据dp数组的含义最后一天后不持有的最大金额为结果}
};
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 。提示
1 k 1001 prices.length 10000 prices[i] 1000
实现代码与解析
动态规划
class Solution {
public:int maxProfit(int k, vectorint prices) {vectorvectorint f(prices.size(), vector(2 * k 1, 0));for (int i 1; i 2 * k; i 2){f[0][i] -prices[0];}for (int i 1; i prices.size(); i){for (int j 1; j 2 * k; j 2){f[i][j] max(f[i - 1][j], f[i - 1][j - 1] - prices[i]);f[i][j 1] max(f[i - 1][j 1], f[i - 1][j] prices[i]);}}return f[prices.size() - 1][2 * k];}
};
原理思路 与上一题完全相同只不过变成了k次买卖只需要根据上一题把数组扩大成2 * k 的大小分别表示第k次持有和不持有状态的最大金额依照上一题根据奇偶写出递推式即可。
