leetcode解题: Integer Break (343)

发表于 | 分类于

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.

Hint:

There is a simple O(n) solution to this problem.
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

解法1：找规律， O(N)

如果把从2到10的结果写出来可以发现，最大的结果是每一个数先分解成3的和，然后和剩下的数的乘积最大。本题还有DP的解法，之后补上

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int integerBreak(int n) {
        if (n == 2 || n == 3) return n - 1;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int integerBreak(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];  // stores the max if split the number into 2 or more numbers
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                int temp = Math.max(dp[j] * dp[i - j], j * (i - j));
                dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(dp[i - j], (i - j)));
            }
        }
        return dp[n];
    }
}