343. Integer Break
Medium
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
DP
Runtime: 0 ms, faster than 100%
Memory Usage: 1.9 MB, less than 88.71%
func integerBreak(n int) int {
dp := make([]int, n + 1)
dp[0] = 0
for i:=1; i<=n; i++ {
max := 0
for j:=0; j<=i/2; j++ {
if j * (i - j) > max {
max = j * (i - j)
}
if dp[j] * dp[i - j] > max {
max = dp[j] * dp[i - j]
}
if dp[j] * (i - j) > max {
max = dp[j] * (i - j)
}
if dp[i - j] * j > max {
max = dp[i - j] * j
}
}
dp[i] = max
}
return dp[n]
}
Last modified 6mo ago