BestDecomposition | Topcoder Archive

Problem Statement

A decomposition of a non-negative integer n is a list of non-negative integers that sum to exactly n. The product of a decomposition is the product of all its members. For example, if n = 4, the following decompositions are possible:

4 = 1+1+1+1, product is 1*1*1*1 = 1.
4 = 1+1+2, product is 1*1*2 = 2.
4 = 1+3, product is 1*3 = 3.
4 = 2+2, product is 2*2 = 4.
4 = 4, product is 4.

Given an int n, determine the decomposition of n with the maximal product, and return that product modulo 10007. In the example above, the maximal product is 4 (the product of the decomposition 2 + 2).

Definition

Class:: BestDecomposition
Method:: maxProduct
Parameters:: int
Returns:: int
Method signature:: int maxProduct(int n)
(be sure your method is public)

Constraints

n will be between 0 and 10000, inclusive.

Examples

```
0
```
```
Returns: 0
```
```
1
```
```
Returns: 1
```
```
5
```
```
Returns: 6
```
5 = 2 + 3, 2 * 3 = 6
```
7
```
```
Returns: 12
```
7 = 3 + 4, 3 * 4 = 12
```
9931
```
```
Returns: 4664
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.