Math
Dynamic Programming
Description
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:
Solutions
Solution 1: Dynamic Programming
We define $f[i]$ as the maximum product that can be obtained by splitting the positive integer $i$, with an initial condition of $f[1] = 1$. The answer is $f[n]$.
Consider the last number $j$ split from $i$, where $j \in [1, i)$. For the number $j$ split from $i$, there are two cases:
Split $i$ into the sum of $i - j$ and $j$, without further splitting, where the product is $(i - j) \times j$;
Split $i$ into the sum of $i - j$ and $j$, and continue splitting, where the product is $f[i - j] \times j$.
Therefore, we can derive the state transition equation:
$$
f[i] = \max(f[i], f[i - j] \times j, (i - j) \times j) \quad (j \in [0, i))
$$
Finally, returning $f[n]$ will suffice.
The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Here, $n$ is the given positive integer.
Python3 Java C++ Go TypeScript Rust JavaScript C# C
class Solution :
def integerBreak ( self , n : int ) -> int :
f = [ 1 ] * ( n + 1 )
for i in range ( 2 , n + 1 ):
for j in range ( 1 , i ):
f [ i ] = max ( f [ i ], f [ i - j ] * j , ( i - j ) * j )
return f [ n ]
1
2
3
4
5
6
7
8
9
10
11
12 class Solution {
public int integerBreak ( int n ) {
int [] f = new int [ n + 1 ] ;
f [ 1 ] = 1 ;
for ( int i = 2 ; i <= n ; ++ i ) {
for ( int j = 1 ; j < i ; ++ j ) {
f [ i ] = Math . max ( Math . max ( f [ i ] , f [ i - j ] * j ), ( i - j ) * j );
}
}
return f [ n ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public :
int integerBreak ( int n ) {
vector < int > f ( n + 1 );
f [ 1 ] = 1 ;
for ( int i = 2 ; i <= n ; ++ i ) {
for ( int j = 1 ; j < i ; ++ j ) {
f [ i ] = max ({ f [ i ], f [ i - j ] * j , ( i - j ) * j });
}
}
return f [ n ];
}
};
func integerBreak ( n int ) int {
f := make ([] int , n + 1 )
f [ 1 ] = 1
for i := 2 ; i <= n ; i ++ {
for j := 1 ; j < i ; j ++ {
f [ i ] = max ( max ( f [ i ], f [ i - j ] * j ), ( i - j ) * j )
}
}
return f [ n ]
}
function integerBreak ( n : number ) : number {
const f = Array ( n + 1 ). fill ( 1 );
for ( let i = 3 ; i <= n ; i ++ ) {
for ( let j = 1 ; j < i ; j ++ ) {
f [ i ] = Math . max ( f [ i ], j * ( i - j ), j * f [ i - j ]);
}
}
return f [ n ];
}
1
2
3
4
5
6
7
8
9
10
11
12
13 impl Solution {
pub fn integer_break ( n : i32 ) -> i32 {
let n = n as usize ;
let mut f = vec! [ 0 ; n + 1 ];
f [ 1 ] = 1 ;
for i in 2 ..= n {
for j in 1 .. i {
f [ i ] = f [ i ]. max ( f [ i - j ] * j ). max (( i - j ) * j );
}
}
f [ n ] as i32
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13 /**
* @param {number} n
* @return {number}
*/
var integerBreak = function ( n ) {
const f = Array ( n + 1 ). fill ( 1 );
for ( let i = 2 ; i <= n ; ++ i ) {
for ( let j = 1 ; j < i ; ++ j ) {
f [ i ] = Math . max ( f [ i ], f [ i - j ] * j , ( i - j ) * j );
}
}
return f [ n ];
};
1
2
3
4
5
6
7
8
9
10
11
12 public class Solution {
public int IntegerBreak ( int n ) {
int [] f = new int [ n + 1 ];
f [ 1 ] = 1 ;
for ( int i = 2 ; i <= n ; ++ i ) {
for ( int j = 1 ; j < i ; ++ j ) {
f [ i ] = Math . Max ( Math . Max ( f [ i ], f [ i - j ] * j ), ( i - j ) * j );
}
}
return f [ n ];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13 #define max(a, b) (((a) > (b)) ? (a) : (b))
int integerBreak ( int n ) {
int * f = ( int * ) malloc (( n + 1 ) * sizeof ( int ));
f [ 1 ] = 1 ;
for ( int i = 2 ; i <= n ; ++ i ) {
f [ i ] = 0 ;
for ( int j = 1 ; j < i ; ++ j ) {
f [ i ] = max ( f [ i ], max ( f [ i - j ] * j , ( i - j ) * j ));
}
}
return f [ n ];
}
Solution 1: Mathematics
When $n < 4$, since the problem requires splitting into at least two integers, $n - 1$ yields the maximum product. When $n \geq 4$, we split into as many $3$s as possible. If the last segment remaining is $4$, we split it into $2 + 2$ for the maximum product.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
Python3 Java C++ Go TypeScript Rust JavaScript C# C
class Solution :
def integerBreak ( self , n : int ) -> int :
if n < 4 :
return n - 1
if n % 3 == 0 :
return pow ( 3 , n // 3 )
if n % 3 == 1 :
return pow ( 3 , n // 3 - 1 ) * 4
return pow ( 3 , n // 3 ) * 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public int integerBreak ( int n ) {
if ( n < 4 ) {
return n - 1 ;
}
if ( n % 3 == 0 ) {
return ( int ) Math . pow ( 3 , n / 3 );
}
if ( n % 3 == 1 ) {
return ( int ) Math . pow ( 3 , n / 3 - 1 ) * 4 ;
}
return ( int ) Math . pow ( 3 , n / 3 ) * 2 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public :
int integerBreak ( int n ) {
if ( n < 4 ) {
return n - 1 ;
}
if ( n % 3 == 0 ) {
return pow ( 3 , n / 3 );
}
if ( n % 3 == 1 ) {
return pow ( 3 , n / 3 - 1 ) * 4 ;
}
return pow ( 3 , n / 3 ) * 2 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12 func integerBreak ( n int ) int {
if n < 4 {
return n - 1
}
if n % 3 == 0 {
return int ( math . Pow ( 3 , float64 ( n / 3 )))
}
if n % 3 == 1 {
return int ( math . Pow ( 3 , float64 ( n / 3 - 1 ))) * 4
}
return int ( math . Pow ( 3 , float64 ( n / 3 ))) * 2
}
1
2
3
4
5
6
7
8
9
10
11
12
13 function integerBreak ( n : number ) : number {
if ( n < 4 ) {
return n - 1 ;
}
const m = Math . floor ( n / 3 );
if ( n % 3 == 0 ) {
return 3 ** m ;
}
if ( n % 3 == 1 ) {
return 3 ** ( m - 1 ) * 4 ;
}
return 3 ** m * 2 ;
}
1
2
3
4
5
6
7
8
9
10
11
12 impl Solution {
pub fn integer_break ( n : i32 ) -> i32 {
if n < 4 {
return n - 1 ;
}
match n % 3 {
0 => return ( 3 as i32 ). pow (( n / 3 ) as u32 ),
1 => return ( 3 as i32 ). pow (( n / 3 - 1 ) as u32 ) * 4 ,
_ => return ( 3 as i32 ). pow (( n / 3 ) as u32 ) * 2 ,
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 /**
* @param {number} n
* @return {number}
*/
var integerBreak = function ( n ) {
if ( n < 4 ) {
return n - 1 ;
}
const m = Math . floor ( n / 3 );
if ( n % 3 == 0 ) {
return 3 ** m ;
}
if ( n % 3 == 1 ) {
return 3 ** ( m - 1 ) * 4 ;
}
return 3 ** m * 2 ;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14 public class Solution {
public int IntegerBreak ( int n ) {
if ( n < 4 ) {
return n - 1 ;
}
if ( n % 3 == 0 ) {
return ( int ) Math . Pow ( 3 , n / 3 );
}
if ( n % 3 == 1 ) {
return ( int ) Math . Pow ( 3 , n / 3 - 1 ) * 4 ;
}
return ( int ) Math . Pow ( 3 , n / 3 ) * 2 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12 int integerBreak ( int n ) {
if ( n < 4 ) {
return n - 1 ;
}
if ( n % 3 == 0 ) {
return ( int ) pow ( 3 , n / 3 );
}
if ( n % 3 == 1 ) {
return ( int ) pow ( 3 , n / 3 - 1 ) * 4 ;
}
return ( int ) pow ( 3 , n / 3 ) * 2 ;
}
GitHub