Algorithm

Problem Name: 343. Integer Break

Problem Link: https://leetcode.com/problems/integer-break/
 

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

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const integerBreak = function(n) {
  const dp = Array(n + 1).fill(0)
  dp[2] = 1
  for(let i = 3; i  < = n; i++) {
    for(let j = 1; j  <  i; j++) {
      dp[i] = Math.max(dp[i], j * Math.max(i - j, dp[i - j]))
    }
  }
  return dp[n]
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
n = 2

Output

x
–
+
cmd
1

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def integerBreak(self, n):
        pre = [0, 1, 1, 2, 4, 6, 9]
        if n < 7:
            return pre[n]
        for i in range(7, n + 1):
            pre.append(max(pre[i - 2] * 2, pre[i - 3] * 3))
        return pre[-1]
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
n = 2

Output

x
–
+
cmd
1

#3 Code Example with C# Programming

Code - C# Programming

start coding...
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Previous
#342 Leetcode Power of Four Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#344 Leetcode - 344. Reverse String Solution in Javascript, C, C++, C#, Java, Python Leetcode