> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/integer-break.md).

# Integer Break

<https://leetcode.com/problems/integer-break/description/>

> Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
>
> For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
>
> Note: You may assume that n is not less than 2 and not larger than 58.

## Thoughts

从1开始往下写几个数，发现从5开始可以利用已知结果求解。假设数i能拆成j和i - j，则f(j)一共有四种情况：f\[i], f(i - j) \* j, f(j) \* (i - j), f(i - j) \* f(j)。比如7能拆成2 + 5，我们需要2和5尽量大，那我们可以选择是否继续拆2和5, 拆的话值最大能是f(2)和f(5)，我们对这四种情况进行下比较即可。

## Code

```
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++) {
                System.out.println(j + ", " + f[j] + ", " + (i - j) + ", " + f[i - j]);
                f[i] = Math.max(f[i], Math.max(j, f[j]) * Math.max(i - j, f[i - j]));
            }
        }

        return f[n];
    }
}
```

## Analysis

做题耗时37 min

时间复杂度O(n^2).

## Ver.2

O(lgN)解法.