Leetcode 343. 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.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

Solution

Breaking the array into several numbers, multiply them to maximize the product of those integers.

In a straightforward way, we search with memorization array.

Solution1. DFS, Time: O(n2), Space: O(n2), 1ms

java

class Solution {
    public int integerBreak(int n) {
        return dfs(n, 0, new int[n + 1][n + 1]);
    }

    private int dfs(int cur, int count, int[][] memo) {
        if (cur == 0 && count >= 2) return 1;
        if (cur <= 0 && count <= 1) return 0;
        if (memo[cur][count] > 0) return memo[cur][count];
        int res = 0;
        int product = 1;
        for (int i = 1; i <= cur; i++) {
            res = Math.max(res, product* i *dfs(cur - i, count + 1, memo));
        }
        memo[cur][count] = res;
        return res;
    }
}

Why is O(n2?)

Because we will do add for n + n - 1 + n - 2 + ... + 1 times.

Python3

import functools

class Solution:
    def integerBreak(self, n: int) -> int:

        @functools.lru_cache
        def dfs(cur, count):
            if cur == 0 and count >= 2:
                return 1
            if cur == 0 and count <= 1:
                return 0
            res, product = 0, 1
            for i in range(1, cur + 1):
                res = max(res, product * i * dfs(cur - i, count + 1))
            return res
        return dfs(n, 0)

Obviously, the straightforward way is too slow. We can speed up in a mathmetic solution.

Considering two tips:

  • when n > 4, (n – 3) * 3 > n.
  • 2 * 2 * 2 < 3 * 3

We need multiply as many as 3s.

So we will get an accepted, O(n) solution:

Solution2. Time: O(n), Space: O(1), 0ms

Java

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        return product * n;
    }
}

Python3

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n - 1
        product = 1
        while n > 4:
            product *= 3
            n -= 3
        return product * n

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号