-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
41 lines (36 loc) · 965 Bytes
/
Solution.cs
File metadata and controls
41 lines (36 loc) · 965 Bytes
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Solution
{
public int MaxProfit(int[] prices, int fee)
{
return MaxProfit_DP(prices, fee);
}
private int MaxProfit_DP(int[] prices, int fee)
{
int[] dp = new int[2];
for (int i = prices.Length - 1; i >= 0; i--)
{
dp[1] = Math.Max(-prices[i] + dp[0], dp[1]);
dp[0] = Math.Max(prices[i] - fee + dp[1], dp[0]);
}
return dp[1];
}
private int MaxProfit_Greedy(int[] prices, int fee)
{
int n = prices.Length;
int maxProfit = 0;
int minPrice = prices[0];
for (int i = 1; i < n; i++)
{
if (prices[i] < minPrice)
{
minPrice = prices[i];
}
else if (prices[i] > minPrice + fee)
{
maxProfit += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return maxProfit;
}
}