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; } |