0%

leetcode Best Time to Buy and Sell Stock

本次题解包括

  • 121 Best Time to Buy and Sell Stock
  • 122 Best Time to Buy and Sell Stock II
  • 123 Best Time to Buy and Sell Stock III
  • 188 Best Time to Buy and Sell Stock IV
  • 714. Best Time to Buy and Sell Stock with Transaction Fee ### 121 Best Time to Buy and Sell Stock

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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

传送门

题意:给定股票每日的售价,求 一次买进和一次卖出最多可以获取多大利润?

思路:其实就是求买进时和卖出是最大差价。每次更新当前最小价格,dp即可。

python

1
2
3
4
5
6
7
8
9
10
class Solution:
# @param prices, a list of integer
# @return an integer
def maxProfit(self, prices):
if not prices : return 0
ans ,money,n = 0 ,prices[0],len(prices)
for i in range(n):
ans=max(ans,prices[i]-money)
money = min(prices[i],money)
return ans

 

122 Best Time to Buy and Sell Stock II

Say you have an array for which the _i_th 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 (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

传送门

题意:给定股票每日的售价,求 若干次买卖最多可以获取多大利润?

思路:其实就是求股票低价买,高价卖最多能获得多少钱。求连续上升的高度和。

如12314为 1买进3卖出1买进4卖出。

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
# @param prices, a list of integer
# @return an integer
def maxProfit(self, prices):
if not prices : return 0
ans ,money,n = 0 ,prices[0],len(prices)
i=0
while i <n:
money = prices[i]
while i+1 < n and prices[i] <= prices[i+1]:
i+=1
ans+=prices[i]-money
i+=1
return ans

 

1
2
3
4
5
6
7
8
9
10
11
class Solution:
# @param prices, a list of integer
# @return an integer
def maxProfit(self, prices):
if not prices : return 0
ans = 0
for i in xrange(1,len(prices)):
if prices[i] > prices[i-1] :
ans += prices[i] - prices[i-1]

return ans

 

123 Best Time to Buy and Sell Stock III

Say you have an array for which the _i_th 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 (ie, you must sell the stock before you buy again).

题目地址:Best Time to Buy and Sell Stock III

题意:给定股票每日的售价,求最多两次买卖最多可以获取多大利润?

思路:DP。

设dp[i]为到第i天能获取的最大值。(类似121题)求出dp后,逆向扫描数组。

nax_price为最大售价,每次减去price[i]得到第i天之后的利润,加上dp[i - 1]即为两次买卖的值。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()) return 0;
vector<int> dp(prices.size(), 0);
int min_price = prices[0];
for(int i = 1; i < prices.size(); ++i){
dp[i] = max(dp[i - 1], prices[i] - min_price);
min_price = min(prices[i], min_price);
}
int ans = dp.back();
int max_price = prices.back();
for(int i = prices.size() - 2; i >= 1; --i){
ans = max(ans, max_price - prices[i] + dp[i - 1]);
max_price = max(max_price, prices[i]);
}
return ans;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices: return 0
dp = [0] * len(prices)
min_price = prices[0]
for i in range(1, len(prices)):
dp[i] = max(dp[i - 1], prices[i] - min_price)
min_price = min(prices[i], min_price)

ans = dp[-1]
max_price = prices[-1]
for i in range(len(prices) - 2, 0, -1):
ans = max(ans, max_price - prices[i] + dp[i - 1])
max_price = max(max_price, prices[i])

return ans

 

188. Best Time to Buy and Sell Stock IV

Say you have an array for which the _i_th 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).

题目地址:Best Time to Buy and Sell Stock IV

题意:给定股票每日的售价,求最多k次买卖最多可以获取多大利润?

思路:dp

设dp[i][x]为第i天第x次交易的最大利润,则容易写出dp方程:

  • dp[i][x] = max(dp[i-1][x] , dp[j][x - 1] + prices[i] - prices[j])  0 <= j < i
  • 上面的状态转移方程第一项为第i天不进行交易,第二项为枚举j 从0~i-1,第j天买入,第i天卖出

注意当k >= len(prices) / 2的时候,说明相当于无限次交易,和第122题Best Time to Buy and Sell Stock II 一样。

上面的复杂度为O(kn^2)代码如下:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.empty()) return 0;
int ans = 0;
if(k >= prices.size() / 2){
for(int i = 1; i < prices.size(); ++i){
if(prices[i] > prices[i - 1])
ans += prices[i] - prices[i - 1];
}
return ans;
}
vector<vector<int>> dp(prices.size(), vector<int>(k + 1, 0));
for(int x = 1; x <= k; ++x){
for(int i = 1; i < prices.size(); ++i){
dp[i][x] = dp[i - 1][x]; // 不做交易
for(int j = 0; j < i; ++j){
dp[i][x] = max(dp[i][x], dp[j][x - 1] + prices[i] - prices[j]);
}
}
ans = max(ans, dp[prices.size() - 1][x]);
}
return ans;
}
};

 

可以对上面的代码优化,注意到枚举j是为了寻找第i天之前交易x-1次的利润最大,而这个过程重复计算了很多,可以进行优化,只需要保存i之前最大的dp[j][x - 1] - prices[j]即可。这样复杂度就变为O(nk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.empty()) return 0;
int ans = 0;
if(k >= prices.size() / 2){
for(int i = 1; i < prices.size(); ++i){
if(prices[i] > prices[i - 1])
ans += prices[i] - prices[i - 1];
}
return ans;
}
vector<vector<int>> dp(prices.size(), vector<int>(k + 1, 0));
for(int x = 1; x <= k; ++x){
int max_pre = -prices[0]; //+ dp[0][x - 1];
for(int i = 1; i < prices.size(); ++i){
dp[i][x] = max(dp[i - 1][x], max_pre + prices[i]);
max_pre = max(max_pre, dp[i][x - 1] - prices[i]);
}
ans = max(ans, dp[prices.size() - 1][x]);
}
return ans;
}
};

空间复杂度上也可以进一步优化为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.empty()) return 0;
int ans = 0;
if(k >= prices.size() / 2){
for(int i = 1; i < prices.size(); ++i){
if(prices[i] > prices[i - 1])
ans += prices[i] - prices[i - 1];
}
return ans;
}
vector<int> dp(prices.size(), 0);
for(int x = 1; x <= k; ++x){
vector<int> ndp(prices.size(), 0);
int max_pre = -prices[0];
for(int i = 1; i < prices.size(); ++i){
ndp[i] = max(ndp[i - 1], max_pre + prices[i]);
max_pre = max(max_pre, dp[i] - prices[i]);
}
ans = max(ans, ndp.back());
dp = ndp;
}
return ans;
}
};

 

之前的写法:

dp,设dp[i][j]为第J天进行第i次交易能获取的最大值。

  • 当k >=n/2时候,相当于第122题。Best Time to Buy and Sell Stock II
  • dp[i][j]=max(dp[i][j-1],prices[j] + maxTemp)  我们能获取的最大利润,当我们在第j天进行抛售时。由于maxTemp已经算了买进时的价格,所以直接加上即可。
  • maxTemp =max(maxTemp,dp[i-1][j-1] - prices[j])  可以理解为已获得的最大利润,即如果买进第j天的,那么用之前一轮的买卖,前一天的的利润即(dp[i-1][j-1])减去prices[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
# @return an integer as the maximum profit
def maxProfit(self, k, prices):
n = len(prices)
if k >= (n>>1):return self.maxProfit2(prices)
dp =[[0 for j in xrange(n)]for i in xrange(k+1)]

for i in xrange(1,k+1):
maxTemp=-prices[0]
for j in xrange(1,n):
dp[i][j]=max(dp[i][j-1],prices[j] + maxTemp)
maxTemp =max(maxTemp,dp[i-1][j-1] - prices[j])
return dp[k][n-1]

def maxProfit2(self,prices):
ans = 0
for i in xrange(1,len(prices)):
if prices[i]>prices[i-1]:
ans +=prices[i]-prices[i-1]
return ans

 


714. Best Time to Buy and Sell Stock with Transaction Fee

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

1
2
3
4
5
6
7
8
9
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation:The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000.

题目地址:leetcode Best Time to Buy and Sell Stock with Transaction Fee

题目大意:给定股票的价格,以及每次交易需要的花费fee,求能获得的最大利润

思路:

双状态DP,类似于Best Time to Buy and Sell Stock with Cooldown

sell 考虑第i天是否卖出,buy考虑第i天是否买入

则有:

  • sell = max(sell, buy + prices[i] - fee)
  • buy = max(buy, sell - prices[i])

C++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
if(prices.size() < 2) return 0;
int sell = 0, buy = -prices[0];
for(int i = 1; i < prices.size(); i++){
sell = max(sell, buy + prices[i] - fee);
buy = max(buy, sell - prices[i]);
}
return sell;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxProfit(int[] prices, int fee) {
if(prices.length < 2) return 0;
int sell = 0, buy = -prices[0];
for(int i = 1; i < prices.length; i++){
sell = Math.max(sell, buy + prices[i] - fee);
buy = Math.max(buy, sell - prices[i]);
}
return sell;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def maxProfit(self, prices, fee):
"""
:type prices: List[int]
:type fee: int
:rtype: int
"""
if len(prices) < 2: return 0
sell = 0
buy = -prices[0]
for i in range(1, len(prices)):
sell = max(sell, buy + prices[i] - fee)
buy = max(buy, sell - prices[i])
return sell

本文是leetcode如下的题解

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~