-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
1043.py
71 lines (67 loc) · 2.38 KB
/
1043.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
__________________________________________________________________________________________________
sample 152 ms submission
class Solution:
def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
dp = [0]*len(A)
max_val = 0
for i in range(K):
if max_val < A[i]:
max_val = A[i]
dp[i] = max_val * (i+1)
for i in range(K, len(A)):
max_val=0
for p in range(0, K):
if A[i-p] > max_val:
max_val = A[i-p]
update = dp[i-p-1] + max_val * (p+1)
if update > dp[i]:
dp[i] = update
return dp[-1]
__________________________________________________________________________________________________
sample 204 ms submission
class Solution:
def helper(self, A, K, i, mem):
if i== len(A):
return
if i < K:
mem.append(max(A[:i+1])*(i+1))
self.helper(A, K, i+1, mem)
else:
best = 0
best_index = None
running = 0
for j in range(i, i-K,-1):
running = max(running,A[j])
r = running*(i-j+1)
l = mem[j-1]
if r+l > best:
best = r+l
best_index = j
mem.append(best)
self.helper(A, K, i+1, mem)
def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
if len(A) == 0:
return 0
mem = []
self.helper(A, K, 0 ,mem)
return mem[-1]
__________________________________________________________________________________________________
sample 232 ms submission
class Solution:
def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
dp_array = []
#First part
max_so_far = A[0]
for i in range(K):
max_so_far = max(max_so_far, A[i])
dp_array.append(max_so_far * (i + 1))
#Second part
for i in range(K, len(A)):
best_option = 0
max_so_far = A[i]
for j in range(i - 1, i - K - 1, -1):
this_option = dp_array[j] + (max_so_far * (i - j))
best_option = max(this_option, best_option)
max_so_far = max(max_so_far, A[j])
dp_array.append(best_option)
return dp_array[-1]