-
Notifications
You must be signed in to change notification settings - Fork 0
/
maximum_profit_dp.py
157 lines (134 loc) · 4.65 KB
/
maximum_profit_dp.py
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
def maximum_profit_unlimited_dp(prices):
"""
A method that calculates the maximum profit that can be made by buying and selling unlimited often
Problem description: https://practice.geeksforgeeks.org/problems/maximum-profit/0
time complexity: O(n)
space complexity: O(n)
Parameters
----------
prices : int[]
a list of int values representing the price of something over a time span
Returns
-------
x : int
the maximum profit that can be made by buying and selling unlimited often
"""
n = len(prices)
if n == 0:
return 0
s, t = [None] * n, [None] * n
s[0], t[0] = -prices[0], 0
for i in range(1, n):
t[i] = max(prices[i] + s[i-1], t[i-1])
s[i] = max(-prices[i] + t[i-1], s[i-1])
return t[n-1]
def maximum_profit_limited_dp(prices, k):
"""
A method that calculates the maximum profit that can be made by buying and selling at most k times
Problem description: https://practice.geeksforgeeks.org/problems/maximum-profit/0
time complexity: O(n*k)
space complexity: O(n*k)
Parameters
----------
prices : int[]
a list of int values representing the price of something over a time span
k : int
integer that restricts how often you can buy and sell
Returns
-------
x : int
the maximum profit that can be made by buying and selling unlimited often
"""
n = len(prices)
if n == 0:
return 0
s = [[0 for _ in range(n)] for _ in range(k+1)]
t = [[0 for _ in range(n)] for _ in range(k+1)]
for i in range(k+1):
s[i][0], t[i][0] = -prices[0], 0
for j in range(1, k+1):
for i in range(1, n):
t[j][i] = max(prices[i] + s[j][i-1], t[j][i-1])
s[j][i] = max(-prices[i] + t[j-1][i-1], s[j][i-1])
return t[k][n-1]
def maximum_profit_limited_spaceoptimized1_dp(prices, k):
"""
A method that calculates the maximum profit that can be made by buying and selling at most k times (space-optimized 1/2)
Problem description: https://practice.geeksforgeeks.org/problems/maximum-profit/0
time complexity: O(n*k)
space complexity: O(n*k)
Parameters
----------
prices : int[]
a list of int values representing the price of something over a time span
k : int
integer that restricts how often you can buy and sell
Returns
-------
x : int
the maximum profit that can be made by buying and selling unlimited often
"""
n = len(prices)
if n == 0:
return 0
s = [0 for _ in range(n)]
t = [[0 for _ in range(n)] for _ in range(k+1)]
s[0] = -prices[0]
for i in range(k+1):
t[i][0] = 0
for j in range(1, k+1):
for i in range(1, n):
t[j][i] = max(prices[i] + s[i-1], t[j][i-1])
s[i] = max(-prices[i] + t[j-1][i-1], s[i-1])
return t[k][n-1]
def maximum_profit_limited_spaceoptimized2_dp(prices, k):
"""
A method that calculates the maximum profit that can be made by buying and selling at most k times (space-optimized 2/2)
Problem description: https://practice.geeksforgeeks.org/problems/maximum-profit/0
time complexity: O(n*k)
space complexity: O(n)
Parameters
----------
prices : int[]
a list of int values representing the price of something over a time span
k : int
integer that restricts how often you can buy and sell
Returns
-------
x : int
the maximum profit that can be made by buying and selling unlimited often
"""
n = len(prices)
if n == 0:
return 0
s = [0 for _ in range(n)]
t = [
[0 for _ in range(n)],
[0 for _ in range(n)]
]
s[0] = -prices[0]
t[0][0] = 0
for _ in range(1, k+1):
for i in range(1, n):
t[1][i] = max(prices[i] + s[i-1], t[1][i-1])
s[i] = max(-prices[i] + t[0][i-1], s[i-1])
t[0] = [e for e in t[1]]
return t[1][n-1]
def max_profit_dp(prices, k):
"""
A method that calculates the maximum profit that can be made by buying and selling at most k times (space-optimized)
Problem description: https://practice.geeksforgeeks.org/problems/maximum-profit/0
time complexity: O(n*k)
space complexity: O(n)
Parameters
----------
prices : int[]
a list of int values representing the price of something over a time span
k : int
integer that restricts how often you can buy and sell
Returns
-------
x : int
the maximum profit that can be made by buying and selling unlimited often
"""
return maximum_profit_limited_spaceoptimized2_dp(prices, k)