-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path343.integer-break.py
More file actions
67 lines (54 loc) · 1.34 KB
/
343.integer-break.py
File metadata and controls
67 lines (54 loc) · 1.34 KB
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
# Tag: Math, Dynamic Programming
# Time: O(N)
# Space: O(N)
# Ref: -
# Note: -
# Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
# Return the maximum product you can get.
#
# Example 1:
#
# Input: n = 2
# Output: 1
# Explanation: 2 = 1 + 1, 1 × 1 = 1.
#
# Example 2:
#
# Input: n = 10
# Output: 36
# Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
#
#
# Constraints:
#
# 2 <= n <= 58
#
#
class Solution:
def integerBreak(self, n: int) -> int:
dp = [1 for i in range(n + 1)]
for i in range(2, n + 1):
for j in range(1, i):
left = max(i - j, dp[i - j])
right = max(j, dp[j])
dp[i] = max(dp[i], left * right)
return dp[n]
class Solution:
def integerBreak(self, n: int) -> int:
dp = [1 for i in range(n + 1)]
for i in range(2, n + 1):
if i > 2:
dp[i] = 2 * max(dp[i - 2], i - 2)
if i > 3:
dp[i] = max(dp[i], 3 * max(dp[i - 3], i - 3))
return dp[n]
class Solution:
def integerBreak(self, n: int) -> int:
if n < 4:
return n - 1
res = 1
while n > 4:
res = res * 3
n -= 3
res = res * n
return res