-
Notifications
You must be signed in to change notification settings - Fork 0
/
BestTimeToBuy&SellPart3.cpp
132 lines (100 loc) · 4.35 KB
/
BestTimeToBuy&SellPart3.cpp
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [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: prices = [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: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
//SOLUTION GIVEN BELOW
class Solution {
public:
int solveRec(int index , int buy , vector<int>&prices, int limit){ // At most two transaction in a day that's why using limit
//base case
if(index == prices.size())
return 0;
if(limit == 0)
return 0;
int profit = 0; // buy = 0 -> not allowed , buy = 1 -> allowed
if(buy){
profit = max((-prices[index] + solveRec(index+1 ,0 , prices ,limit)) ,(0+solveRec(index+1 , 1 , prices ,limit)));
}
else{ // limit -1 -> one trasaction is completed
profit = max((+prices[index]+solveRec(index+1 ,1, prices ,limit-1)) , (0+solveRec(index+1 ,0, prices ,limit)));
}
return profit;
}
int solveMem(int index , int buy ,vector<int>&prices, int limit ,vector<vector<vector<int>>>&dp){
if(index >= prices.size())
return 0;
if(limit == 0)
return 0;
if(dp[index][buy][limit] != -1)
return dp[index][buy][limit];
int profit = 0;
if(buy){
profit = max((-prices[index] + solveMem(index+1 ,0 , prices ,limit,dp)) ,(0+solveMem(index+1 , 1 , prices ,limit,dp)));
}
else{
profit = max((+prices[index]+solveMem(index+1 ,1, prices ,limit-1,dp)) , (0+solveMem(index+1 ,0, prices ,limit,dp)));
}
return dp[index][buy][limit] = profit;
}
int solveTab(vector<int>&prices){
int n = prices.size();
vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(2 , vector<int>(3,0)));
for(int index = n-1;index>=0;index--){
for(int buy =0;buy <=1;buy++){
for(int limit = 1;limit <= 2;limit++){
int profit = 0;
if(buy){
profit = max((-prices[index] + dp[index+1][0][limit]) ,(0+ dp[index+1][1][limit]));
}
else{
profit = max((+prices[index]+ dp[index+1][1][limit-1]) , (0+dp[index+1][0][limit]));
}
dp[index][buy][limit] = profit;
}
}
}
return dp[0][1][2];
}
int solveSpaceOptimization(vector<int>&prices){
int n = prices.size();
vector<vector<int>> curr(2,vector<int>(3,0));
vector<vector<int>>next (2, vector<int>(3,0));
for(int index = n-1;index>=0;index--){
for(int buy =0;buy <=1;buy++){
for(int limit = 1;limit <= 2;limit++){
int profit = 0;
if(buy){
profit = max((-prices[index] + next[0][limit]) ,(0+ next[1][limit]));
}
else{
profit = max((+prices[index]+ next[1][limit-1]) , (0+next[0][limit]));
}
curr[buy][limit] = profit;
}
}
next = curr;
}
return next[1][2];
}
int maxProfit(vector<int>& prices) {
int n = prices.size();
// return solveRec(0 ,1 ,prices , 2);
// vector<vector<vector<int>>> dp(n,vector<vector<int>>(2 , vector<int>(3,-1)));
// return solveMem(0 ,1, prices , 2, dp);
// return solveTab(prices);
return solveSpaceOptimization(prices);
}
};