Skip to content

Commit 166efbb

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0123. Best Time to Buy and Sell Stock III
1 parent 988b0c8 commit 166efbb

File tree

9 files changed

+216
-94
lines changed

9 files changed

+216
-94
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -174,6 +174,7 @@
174174
- [最佳观光组合](./solution/1000-1099/1014.Best%20Sightseeing%20Pair/README.md)
175175
- [买卖股票的最佳时机](./solution/0100-0199/0121.Best%20Time%20to%20Buy%20and%20Sell%20Stock/README.md)
176176
- [买卖股票的最佳时机 II](./solution/0100-0199/0122.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20II/README.md)
177+
- [买卖股票的最佳时机 III](./solution/0100-0199/0123.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20III/README.md)
177178
- [最佳买卖股票时机含冷冻期](./solution/0300-0399/0309.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Cooldown/README.md)
178179
- [买卖股票的最佳时机含手续费](./solution/0700-0799/0714.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Transaction%20Fee/README.md)
179180
- [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -168,6 +168,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
168168
- [Best Sightseeing Pair](./solution/1000-1099/1014.Best%20Sightseeing%20Pair/README_EN.md)
169169
- [Best Time to Buy and Sell Stock](./solution/0100-0199/0121.Best%20Time%20to%20Buy%20and%20Sell%20Stock/README_EN.md)
170170
- [Best Time to Buy and Sell Stock II](./solution/0100-0199/0122.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20II/README_EN.md)
171+
- [Best Time to Buy and Sell Stock III](./solution/0100-0199/0123.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20III/README_EN.md)
171172
- [Best Time to Buy and Sell Stock with Cooldown](./solution/0300-0399/0309.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Cooldown/README_EN.md)
172173
- [Best Time to Buy and Sell Stock with Transaction Fee](./solution/0700-0799/0714.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Transaction%20Fee/README_EN.md)
173174
- [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)

‎solution/0100-0199/0123.Best Time to Buy and Sell Stock III/README.md

Lines changed: 88 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -55,27 +55,113 @@
5555
<li><code>0 <= prices[i] <= 10<sup>5</sup></code></li>
5656
</ul>
5757

58-
5958
## 解法
6059

6160
<!-- 这里可写通用的实现逻辑 -->
6261

62+
动态规划法。
63+
64+
设 f1 表示第 1 次买入股票后的最大利润，f2 表示第 1 次卖出股票后的最大利润，f3 表示第 2 次买入股票后的最大利润，f4 表示第 2 次卖出股票后的最大利润。
65+
66+
遍历过程中，直接使用 f1, f2, f3, f4 计算，考虑的是在同一天买入和卖出时，收益是 0，不会对答案产生影响。
67+
68+
最后返回 f2 即可。
69+
6370
<!-- tabs:start -->
6471

6572
### **Python3**
6673

6774
<!-- 这里可写当前语言的特殊实现逻辑 -->
6875

6976
```python
70-
77+
class Solution:
78+
def maxProfit(self, prices: List[int]) -> int:
79+
# 第一次买入，第一次卖出，第二次买入，第二次卖出
80+
f1, f2, f3, f4 = -prices[0], 0, -prices[0], 0
81+
for price in prices[1:]:
82+
f1 = max(f1, -price)
83+
f2 = max(f2, f1 + price)
84+
f3 = max(f3, f2 - price)
85+
f4 = max(f4, f3 + price)
86+
return f4
7187
```
7288

7389
### **Java**
7490

7591
<!-- 这里可写当前语言的特殊实现逻辑 -->
7692

7793
```java
94+
class Solution {
95+
public int maxProfit(int[] prices) {
96+
// 第一次买入，第一次卖出，第二次买入，第二次卖出
97+
int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
98+
for (int i = 1; i < prices.length; ++i) {
99+
f1 = Math.max(f1, -prices[i]);
100+
f2 = Math.max(f2, f1 + prices[i]);
101+
f3 = Math.max(f3, f2 - prices[i]);
102+
f4 = Math.max(f4, f3 + prices[i]);
103+
}
104+
return f4;
105+
}
106+
}
107+
```
108+
109+
### **C++**
110+
111+
```cpp
112+
class Solution {
113+
public:
114+
int maxProfit(vector<int>& prices) {
115+
int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
116+
for (int i = 1; i < prices.size(); ++i) {
117+
f1 = max(f1, -prices[i]);
118+
f2 = max(f2, f1 + prices[i]);
119+
f3 = max(f3, f2 - prices[i]);
120+
f4 = max(f4, f3 + prices[i]);
121+
}
122+
return f4;
123+
}
124+
};
125+
```
126+
127+
### **Go**
128+
129+
```go
130+
func maxProfit(prices []int) int {
131+
f1, f2, f3, f4 := -prices[0], 0, -prices[0], 0
132+
for i := 1; i < len(prices); i++ {
133+
f1 = max(f1, -prices[i])
134+
f2 = max(f2, f1 + prices[i])
135+
f3 = max(f3, f2 - prices[i])
136+
f4 = max(f4, f3 + prices[i])
137+
}
138+
return f4
139+
}
140+
141+
func max(a, b int) int {
142+
if a > b {
143+
return a
144+
}
145+
return b
146+
}
147+
```
78148

149+
### **C#**
150+
151+
```cs
152+
public class Solution {
153+
public int MaxProfit(int[] prices) {
154+
int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
155+
for (int i = 1; i < prices.Length; ++i)
156+
{
157+
f1 = Math.Max(f1, -prices[i]);
158+
f2 = Math.Max(f2, f1 + prices[i]);
159+
f3 = Math.Max(f3, f2 - prices[i]);
160+
f4 = Math.Max(f4, f3 + prices[i]);
161+
}
162+
return f4;
163+
}
164+
}
79165
```
80166

81167
### **...**

‎solution/0100-0199/0123.Best Time to Buy and Sell Stock III/README_EN.md

Lines changed: 78 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,13 +59,90 @@ Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
5959
### **Python3**
6060

6161
```python
62-
62+
class Solution:
63+
def maxProfit(self, prices: List[int]) -> int:
64+
f1, f2, f3, f4 = -prices[0], 0, -prices[0], 0
65+
for price in prices[1:]:
66+
f1 = max(f1, -price)
67+
f2 = max(f2, f1 + price)
68+
f3 = max(f3, f2 - price)
69+
f4 = max(f4, f3 + price)
70+
return f4
6371
```
6472

6573
### **Java**
6674

6775
```java
76+
class Solution {
77+
public int maxProfit(int[] prices) {
78+
int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
79+
for (int i = 1; i < prices.length; ++i) {
80+
f1 = Math.max(f1, -prices[i]);
81+
f2 = Math.max(f2, f1 + prices[i]);
82+
f3 = Math.max(f3, f2 - prices[i]);
83+
f4 = Math.max(f4, f3 + prices[i]);
84+
}
85+
return f4;
86+
}
87+
}
88+
```
89+
90+
### **C++**
91+
92+
```cpp
93+
class Solution {
94+
public:
95+
int maxProfit(vector<int>& prices) {
96+
int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
97+
for (int i = 1; i < prices.size(); ++i) {
98+
f1 = max(f1, -prices[i]);
99+
f2 = max(f2, f1 + prices[i]);
100+
f3 = max(f3, f2 - prices[i]);
101+
f4 = max(f4, f3 + prices[i]);
102+
}
103+
return f4;
104+
}
105+
};
106+
```
107+
108+
### **Go**
109+
110+
```go
111+
func maxProfit(prices []int) int {
112+
f1, f2, f3, f4 := -prices[0], 0, -prices[0], 0
113+
for i := 1; i < len(prices); i++ {
114+
f1 = max(f1, -prices[i])
115+
f2 = max(f2, f1 + prices[i])
116+
f3 = max(f3, f2 - prices[i])
117+
f4 = max(f4, f3 + prices[i])
118+
}
119+
return f4
120+
}
121+
122+
func max(a, b int) int {
123+
if a > b {
124+
return a
125+
}
126+
return b
127+
}
128+
```
68129

130+
### **C#**
131+
132+
```cs
133+
public class Solution {
134+
public int MaxProfit(int[] prices) {
135+
int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
136+
for (int i = 1; i < prices.Length; ++i)
137+
{
138+
f1 = Math.Max(f1, -prices[i]);
139+
f2 = Math.Max(f2, f1 + prices[i]);
140+
f3 = Math.Max(f3, f2 - prices[i]);
141+
f4 = Math.Max(f4, f3 + prices[i]);
142+
}
143+
return f4;
144+
}
145+
}
69146
```
70147

71148
### **...**

‎solution/0100-0199/0123.Best Time to Buy and Sell Stock III/Solution.cpp

Lines changed: 7 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1,44 +1,13 @@
11
class Solution {
22
public:
33
int maxProfit(vector<int>& prices) {
4-
int left = 0;
5-
int len = prices.size();
6-
if(len == 0 || len == 1)return 0;
7-
8-
vector<int> leftArr(len, 0);
9-
vector<int> rightArr(len, 0);
10-
11-
int diff, day = 1, minPrice, maxPrice, maxProfit;
12-
13-
//计算某一天及之前的最大利益
14-
minPrice = prices[0];
15-
maxProfit = 0;
16-
for (day = 1; day < len; day++) {
17-
diff = prices[day] - minPrice;
18-
if (diff < 0)minPrice = prices[day];
19-
else if (diff > maxProfit)maxProfit = diff;
20-
21-
leftArr[day] = maxProfit;
22-
}
23-
24-
//计算某一天及之前的最大利益
25-
maxPrice = prices[len - 1];
26-
maxProfit = 0;
27-
for (day = len - 2; day >= 0; day--) {
28-
diff = maxPrice - prices[day];
29-
if (diff < 0)maxPrice = prices[day];
30-
else if (diff > maxProfit)maxProfit = diff;
31-
32-
rightArr[day] = maxProfit;
4+
int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
5+
for (int i = 1; i < prices.size(); ++i) {
6+
f1 = max(f1, -prices[i]);
7+
f2 = max(f2, f1 + prices[i]);
8+
f3 = max(f3, f2 - prices[i]);
9+
f4 = max(f4, f3 + prices[i]);
3310
}
34-
35-
int sum = 0;
36-
maxProfit = leftArr[0] + rightArr[0];
37-
for (int i = 1; i < len; i++) {
38-
sum = leftArr[i] + rightArr[i];
39-
if (sum > maxProfit)maxProfit = sum;
40-
}
41-
42-
return maxProfit;
11+
return f4;
4312
}
4413
};

‎solution/0100-0199/0123.Best Time to Buy and Sell Stock III/Solution.cs

Lines changed: 7 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -1,37 +1,13 @@
1-
using System;
2-
31
public class Solution {
42
public int MaxProfit(int[] prices) {
5-
int[] leftProfit = new int[prices.Length];
6-
int[] rightProfit = new int[prices.Length];
7-
8-
// iterate from left to right
9-
var minPrice = int.MaxValue;
10-
var leftMaxProfit = 0;
11-
for (var i = 0; i < prices.Length; ++i)
3+
int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
4+
for (int i = 1; i < prices.Length; ++i)
125
{
13-
minPrice = Math.Min(minPrice, prices[i]);
14-
leftMaxProfit = Math.Max(leftMaxProfit, prices[i] - minPrice);
15-
leftProfit[i] = leftMaxProfit;
6+
f1 = Math.Max(f1, -prices[i]);
7+
f2 = Math.Max(f2, f1 + prices[i]);
8+
f3 = Math.Max(f3, f2 - prices[i]);
9+
f4 = Math.Max(f4, f3 + prices[i]);
1610
}
17-
18-
// iterate from right to left
19-
var maxPrice = int.MinValue;
20-
var rightMaxProfit = 0;
21-
for (var i = prices.Length - 1; i >= 0; --i)
22-
{
23-
maxPrice = Math.Max(maxPrice, prices[i]);
24-
rightMaxProfit = Math.Max(rightMaxProfit, maxPrice - prices[i]);
25-
rightProfit[i] = rightMaxProfit;
26-
}
27-
28-
// merge two profits
29-
var maxProfit = 0;
30-
for (var i = 0; i < prices.Length; ++i)
31-
{
32-
maxProfit = Math.Max(maxProfit, leftProfit[i] + rightProfit[i]);
33-
}
34-
35-
return maxProfit;
11+
return f4;
3612
}
3713
}

‎solution/0100-0199/0123.Best Time to Buy and Sell Stock III/Solution.go

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
func maxProfit(prices []int) int {
2+
f1, f2, f3, f4 := -prices[0], 0, -prices[0], 0
3+
for i := 1; i < len(prices); i++ {
4+
f1 = max(f1, -prices[i])
5+
f2 = max(f2, f1 + prices[i])
6+
f3 = max(f3, f2 - prices[i])
7+
f4 = max(f4, f3 + prices[i])
8+
}
9+
return f4
10+
}
11+
12+
func max(a, b int) int {
13+
if a > b {
14+
return a
15+
}
16+
return b
17+
}

‎solution/0100-0199/0123.Best Time to Buy and Sell Stock III/Solution.java

Lines changed: 10 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,13 @@
1-
class Solution {
2-
public int maxProfit(int[] prices) {
3-
if (prices.length <= 1) return 0;
4-
int m = 2 , n = prices.length;
5-
int[][] dp = new int[m+1][n];
6-
for (int i = 1; i <= m; i++) {
7-
int maxdiff = Integer.MIN_VALUE;
8-
for (int j = 1; j < n; j++) {
9-
maxdiff = Math.max(maxdiff, dp[i-1][j-1] - prices[j-1]);
10-
dp[i][j] = Math.max(dp[i][j-1], prices[j] + maxdiff);
11-
}
1+
public class Solution {
2+
public int MaxProfit(int[] prices) {
3+
int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
4+
for (int i = 1; i < prices.Length; ++i)
5+
{
6+
f1 = Math.Max(f1, -prices[i]);
7+
f2 = Math.Max(f2, f1 + prices[i]);
8+
f3 = Math.Max(f3, f2 - prices[i]);
9+
f4 = Math.Max(f4, f3 + prices[i]);
1210
}
13-
return dp[m][n-1];
11+
return f4;
1412
}
1513
}

‎solution/0100-0199/0123.Best Time to Buy and Sell Stock III/Solution.py

Lines changed: 7 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,9 @@
11
class Solution:
22
def maxProfit(self, prices: List[int]) -> int:
3-
length = len(prices)
4-
if 0 == length:
5-
return 0
6-
dp = [([0] * length) for i in range(3)]
7-
for i in range(1, 3, 1):
8-
maxdiff = -((1 << 31) - 1)
9-
for j in range(1, length, 1):
10-
maxdiff = max(maxdiff, dp[i-1][j-1] - prices[j-1])
11-
dp[i][j] = max(dp[i][j - 1], maxdiff + prices[j])
12-
return dp[2][length - 1]
3+
f1, f2, f3, f4 = -prices[0], 0, -prices[0], 0
4+
for price in prices[1:]:
5+
f1 = max(f1, -price)
6+
f2 = max(f2, f1 + price)
7+
f3 = max(f3, f2 - price)
8+
f4 = max(f4, f3 + price)
9+
return f4

0 commit comments

Comments
 (0)