# Leetcode Integer Break problem solution

In this Leetcode Integer Break problem solution you have 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.

## Problem solution in Python.

```class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""

if n == 2: return 1
if n == 3: return 2
if n == 4: return 4
if n % 3 == 0: return 3**(n/3)
if (n-4)%3 == 0:
return 3**((n-4)/3)*4
else:
return 3**((n-2)/3)*2
```

## Problem solution in Java.

```class Solution {
int[] dp;
public int integerBreak(int n) {
dp = new int[n+1];
Arrays.fill(dp, -1);
dp[0] = 1;
return helper(n, 0);
}

public int helper(int n, int time)
{
if(dp[n]>0)return dp[n];
int res = 0;
for(int i = 1; i < n; i++)
{
res = Math.max(res, helper(n-i, time+1) * i);
}

if(time>=1){
res = Math.max(res, n);
}

dp[n] = res;
return res;
}
}
```

## Problem solution in C++.

```class Solution {
public:
map<int,int>mp;
int integerBreak(int n) {
mp[1]=1;
if(mp.find(n)!=mp.end())
return mp[n];
int mx=INT_MIN;
for(int i=1;i<=n/2;i++)
mx=max(mx,max(i,integerBreak(i))*max(n-i,integerBreak(n-i)));
mp[n]=mx;
return mx;
}
};
```

## Problem solution in C.

```#define MAX(N,M) (N > M ? N : M)
int my_integerBreak(int n, int *dp) {
if (n <= 1) {
return 1;
}
if (n == 2) {
return 2;
}

if (n == 3) {
return 3;
}

if (dp[n] == -1) {
dp[n] = MAX( 2 * my_integerBreak(n-2, dp), 3 * my_integerBreak(n-3, dp));
}

return dp[n];
}

int integerBreak(int n){

if (n <=1 ) {
return 1;
}

if (n == 2) {
return 1;
}

if (n == 3) {
return 2;
}

int *dp = (int *)malloc(sizeof(int) * (n+1));
memset(dp, -1, sizeof(int) * (n + 1));

dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
return MAX (2*my_integerBreak(n-2, dp), 3*my_integerBreak(n-3, dp));
}
```