LeetCode – Separación de enteros (Java)

Dado un número entero positivo n, divídalo en la suma de al menos dos números enteros positivos y maximice el producto de esos números enteros. Devuelva el producto máximo que pueda obtener.

Por ejemplo, dado n = 2, devuelve 1 (2 = 1 + 1); dado n = 10, devuelve 36 (10 = 3 + 3 + 4).

Solución Java 1 – Programación dinámica

Deja dp[i] para ser el valor máximo de producción para romper el número i. Desde dp[i+j] puede ser i * j, dp[i+j] = max (max (dp[i], i) * máx (dp[j], j)), dp[i+j]).

public int integerBreak(int n) {
    int[] dp = new int[n+1];
 
    for(int i=1; i<n; i++){
        for(int j=1; j<i+1; j++){
            if(i+j<=n){
                dp[i+j]=Math.max(Math.max(dp[i],i)*Math.max(dp[j],j), dp[i+j]);
            }
        }
    }
 
    return dp[n];
}

Solución Java 2: uso de regularidades

Si vemos el resultado de ruptura de algunos números, podemos ver un patrón repetido como el siguiente:

2 -> 1*1
3 -> 1*2
4 -> 2*2
5 -> 3*2
6 -> 3*3
7 -> 3*4
8 -> 3*3*2
9 -> 3*3*3
10 -> 3*3*4
11 -> 3*3*3*2

Solo necesitamos encontrar cuántos 3 podemos obtener cuando n> 4. Si n% 3 == 1, no queremos que 1 sea uno de los números rotos, queremos 4.

public int integerBreak(int n) {
 
    if(n==2) return 1;
    if(n==3) return 2;
    if(n==4) return 4;
 
    int result=1;
    if(n%3==0){
        int m = n/3;
        result = (int) Math.pow(3, m);
    }else if(n%3==2){
        int m=n/3;
        result = (int) Math.pow(3, m) * 2;
    }else if(n%3==1){
        int m=(n-4)/3;
        result = (int) Math.pow(3, m) *4;
    }
 
    return result;
}