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]
}