Separación de enteros

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.

Solución: Sabía que se trataba de dp. Me puse en marcha teniendo esto en cuenta. Entonces suponga que tenemos una solución para n -1 y estamos viendo el número n. este valor serían dos números cuya suma sea igual a n. Este número puede ser cualquiera del rango (1 .. n- 1). Tenga en cuenta que tendríamos que correr hasta la mitad de la lista ya que después de la mitad no habría ninguna contraparte cuya suma sea igual an. Llegué a esto bastante rápido, pero el tiempo que me tomé tal vez porque estaba hambriento fue el hecho de que, además de esto, debemos considerar los números k, n- k

Agregar esto resolvió el problema

Segundo enfoque

Digamos que tenemos un número n y encontramos dos números xey tales que x + y = n. ahora el producto es x * y. Si fuera posible dividir xey en dos números enteros z y ay c y d tales que z + a = x y c + d = y tales que z * a & gt; xyc * d & gt; y. Luego debemos dividir dos enteros más

así que digamos f = z * (x-a)

si x es impar, será el máximo cuando a = (x + 1) / 2 y z = (x-1) / 2

si x es par, será máximo cuando a = z = x / 2

ahora necesitamos romper más cuando

max (f) & gt; xo cuando x es par

x2 / 4 & gt; x esto significa x & gt; 4

cuando x es impar, esto significa que x & gt; 5

así que hasta que nuestro número sea menor que 4 lo seguimos rompiendo

Deberíamos romper los números & gt; 4 de tal manera que no necesite más rupturas, lo que significa que la ruptura debe contener números & lt; 4 que sea 1, 2, 3.

Ahora 1 no hace mucho por el producto, por lo que quedan 2 y 3. deberíamos tener más de 3 en lugar de más de 2 porque

digamos que para 6 3 * 3 & gt; 2 * 2 * 2

así que hasta que el número sea menor que 4 seguimos agregando 3 a la lista de factores. Como agregamos 3 a la lista de factores, el número ahora se convierte en n-3 y así sucesivamente hasta que n sea menor que 4