Разбиение числа на сумму с максимальным произведнием слагаемых

Источник: https://leetcode.com/problems/integer-break/

Дано целое число n, нужно представить его в виде суммы k положительных целых чисел, где k >= 2, и произведение этих чисел максимально.

Вернуть максимальное произведение.

Пример 1:

Дано: n = 2
Результат: 1
Пояснение: 2 = 1 + 1, 1 × 1 = 1.

Пример 2:

Дано: n = 10
Результат: 36
Пояснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Ограничения:

• 2 <= n <= 58


Идея решения

Допустим мы представили число n в виде суммы, и произведение слагаемых этой суммы обозначим P = p1 * p2 * ... pk.

Рассмотрим некое слагаемое pi uи представим его в виде суммы pi-2 и 2. Если 2(pi-2) > pi, то у нас получится ещё большее произведение, и это имеет место при pi > 4.

Рассмотрим сумму pi-3 и 3, тогда 3*(pi-3) > pi при pi > 4.5.

Если pi= 4, то (4-2)*2=4, а (4-3)*3=3. То есть

Таким образом, нам нужно разбить исходное число на сумму двоек и троек, чтобы получить максимальное произведение. 

В итоге нам нужно представить n = a3 + b2, так чтобы P = (3^a) * (2^b) было максимальным. А для этого нужно отдать предпочтение тройкам, насколько это возможно.

Действительно (pi-2)2 сравним с (pi-3)*3. При каких pi использование троек будет предпочтительнее?
(pi-2)2  <= (pi-3)*3
2pi-4 <= 3pi-9
5<=pi

Если pi равно 2 или 3, то мы не можем дальше раскладывать эту сумму. Если pi=4, то его тогже оставляем.

В итоге у нас есть 3 возможных КЕЙСА для представления числа n:

1. Если n = a*3 то результат будет 3^a.
2. Если n = a3 + 2, то результат будет 2(3^a).
3. Если n = a3 + 2*2 (pi=4), то результат будет 2 * 2 * 3^a

Самая трудоемкая операция при таком подходе -это функция Math.pow(), которая требует O(log n) tвремени - это и будет сложность всего алгоритма.

 

Имплементация

public class Solution {
    public int integerBreak(int n) {
        if(n == 2)
            return 1; // 2=1+1, 1*1=1
        else if(n == 3)
            return 2; // 3=1+2, 1*2=2
        else if(n%3 == 0) // кейс 1
            return (int)Math.pow(3, n/3);
        else if(n%3 == 1) // кейс 3
            return 2 * 2 * (int) Math.pow(3, (n - 4) / 3);
        else // кейс 2
            return 2 * (int) Math.pow(3, n/3);
    }
            
}