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)解法.