Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
class Solution { public: int maxProfit(vector<int>& prices) { // 方法1 int max = 0; for (int i=0; i<prices.size(); i++){ for (int j=i+1; j<prices.size(); j++){ if (prices[j]-prices[i] > max) max = prices[j]-prices[i]; } } return max; // 方法2 if (prices.empty()) return 0; int i=prices.size()-1, ans=0, maxp=prices[i]; for (--i; i>=0; --i){ ans=max(ans, maxp-prices[i]); maxp=max(maxp, prices[i]); // 逆向，维护一个max } return ans; } };
==================================================================================================================
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
class Solution { public: int maxProfit(vector<int>& prices) { // 贪心法: 只要相邻的两天股票的价格是上升的, 我们就进行一次交易, 获得一定利润. // 这样的策略不一定是最小的交易次数, 但是一定会得到最大的利润. int max = 0; for (int i=1; i<prices.size(); i++){ if (prices[i]-prices[i-1]>0) max += (prices[i]-prices[i-1]); } return max; } };
====================================================================================================================
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
https://zhuanlan.zhihu.com/p/53849130
class Solution: def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ nums = len(prices) if nums <= 1: return 0 leftoright = [0 for _ in range(nums)] # [0, 0, 0, ...] minprice = prices[0] # 先从左往右遍历，在只允许进行一次交易的前提下：求一遍最大利润 # 即以当前价格为卖出价格 for i in range(1, nums): # 更新买入价格的最小值 minprice = min(minprice, prices[i]) # 从第0天到第i天，获取最大利润 # 若当天什么都不做，则获得前一天的利润； # 若当前进行一次交易，则利润为当天价格（卖出价格）减去前面最低点的价格 # 于是当天的最大利润为上面两种情况的最大值 leftoright[i] = max(leftoright[i-1], prices[i]-minprice) maxprice = prices[-1] rightoleft = [0 for _ in range(nums)] # 再从右往左遍历，在只允许进行一次交易的前提下：求一遍最大利润 # 即以当天价格为买入价格 for i in range(nums-2, -1, -1): # 更新卖出价格的最大值 maxprice = max(prices[i], maxprice) # 同上，若第i天什么都不做，则获利为第i+天的利润， # 若进行一次交易，则利润为当天价格减去最高卖出价格 # 于是当天的最大利润为上面两种情况的最大值 rightoleft[i] = max(rightoleft[i+1], maxprice-prices[i]) # 将对应位置一一求和，即为在最多允许两次交易的情况下的最大利润 res = [x+y for x, y in zip(leftoright, rightoleft)] return max(res)
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
解题思路
求最优解通常是动态规划的一个明显特征。假设：
- local[i][j]表示最后一次买卖在第i天卖出，同时交易次数小于等于j次的最大收益；
- glocal[i][j]表示前i天完成小于等于j次交易的最大收益。
下面，我们先来推导local[i][j]的状态转移方程。local[i][j]表示最后一次买卖在第i天卖出，同时交易次数小于等于j次的最大收益，那么最后一次买卖的买入时刻存在两种情况：最后一次买卖在第i-1天买入和最后一次买卖的第i-1天前买入。
- 最后一次买卖在第i-1天买入：local[i][j]=global[i-1][j-1] + prices[i] - prices[i-1]。其中，prices[i] - prices[i-1]表示最后一次买卖股票的收入，global[i-1][j-1]表示之前i-1天完成小于等于j-1次交易的最大收益。
- 最后一次买卖在第i-1天前买入：local[i][j]=local[i-1][j]+prices[i]-prices[i-1]。其中，prices[i] - prices[i-1]表示最后一次买卖股票的收入，local[i-1][j]表示完成小于等于j次交易且最后一次交易在第i-1天完成的最大收益。这里有的同学可能存在疑问，为什么可以这样推导。
原因是，当你在第i-1天卖出完成第j次买卖时，如果你在这一天再次买入，并在下一天卖出，此时的交易等同于在第i-1天不卖出，等到第i天再卖出，因此交易次数依然为j次，不会增加交易次数！
通过上面的两步分析，我们可以知道，local[i][j]是这两种情况中的最优解，我们得到状态转移方程如下：
接下来，我们分析上式中global[i][j]的状态转移方程。glocal[i][j]表示前i天完成小于等于j次交易的最大收益，它可能来自两种情况：
- 在前i-1天完成小于等于j次交易的最大收益，即global[i-1][j]；
- 在第i天完成小于等于j次交易的最大收益，即local[i][j]。
因此，得到global[i][j]的状态转移方程如下：
到这里，这道题目已经得以解决，时间复杂度为O(N*K)。当K非常大时，时间成本会上升，这里可以进一步优化：如果K≥N/2K≥N/2，那么等同于你可以进行无限次交易(K超过了可供交易的最大次数)，那么你只要贪心的进行买卖就可以了(如果股票下跌，就在下跌前买入，下跌后卖出)。此时，时间复杂度为O(N)。
OK，到这里，完美解决。真的完美了吗？如果想进一步优化代码空间复杂度的同学可以接着往下看。
在求解local[i][j]的过程中，你会发现，他依赖于global[i-1][j-1]和local[i-1][j]，我们并不真的需要第一个维度，可以把它简化如下：
是不是很神奇？因为local[i][j]只依赖于local[i-1][j]，而不依赖于local[i-2][j]，因此我们可以在求解local[i][j]的同时，覆盖之前的local[i-1][j]的值(它已经不需要了)。
同理，global[i][j]的求解可以简化如下：
这里有一点需要注意，因为local[i][j]的求解依赖于global[i-1][j-1]，如果从左向右更新local和global的数组的话，global[j-1]此时已经被刷新为global[i][j-1]，而local[j]求解需要的是global[i-1][j-1]，global居然被提前更新了！因此，不能从左向右更新local和global数组，而是需要从右向左更新，这样可以保证每次计算local[j]时，使用的是global[i-1][j]，而不是global[i][j]！
代码实现
class Solution { public: int maxProfit(int k, vector<int> &prices) { int max_profit = 0; if (k >= prices.size() / 2) { for (int i = 1; i < prices.size(); ++i) { if (prices[i] - prices[i - 1] > 0) { max_profit += prices[i] - prices[i - 1]; } } } else { vector<int> local(k+1); vector<int> global(k+1); for (int i = 1; i < prices.size(); ++i) { for (int j = k; j >= 1; --j) { local[j] = max(global[j - 1], local[j]) + prices[i] - prices[i - 1]; global[j] = max(global[j], local[j]); } } max_profit = global[k]; } return max_profit; } };