Dado un número n, podemos dividirlo en solo tres partes n/2, n/3 y n/4 (consideraremos solo la parte entera). La tarea es encontrar la suma máxima que podemos hacer dividiendo el número en tres partes recursivamente y sumándolas juntas.
Ejemplos:
Input : n = 12
Output : 13
// We break n = 12 in three parts {12/2, 12/3, 12/4}
// = {6, 4, 3}, now current sum is = (6 + 4 + 3) = 13
// again we break 6 = {6/2, 6/3, 6/4} = {3, 2, 1} = 3 +
// 2 + 1 = 6 and further breaking 3, 2 and 1 we get maximum
// summation as 1, so breaking 6 in three parts produces
// maximum sum 6 only similarly breaking 4 in three
// parts we can get maximum sum 4 and same for 3 also.
// Thus maximum sum by breaking number in parts is=13
Input : n = 24
Output : 27
// We break n = 24 in three parts {24/2, 24/3, 24/4}
// = {12, 8, 6}, now current sum is = (12 + 8 + 6) = 26
// As seen in example, recursively breaking 12 would
// produce value 13. So our maximum sum is 13 + 8 + 6 = 27.
// Note that recursively breaking 8 and 6 doesn't produce
// more values, that is why they are not broken further.
Input : n = 23
Output : 23
// we break n = 23 in three parts {23/2, 23/3, 23/4} =
// {10, 7, 5}, now current sum is = (10 + 7 + 5) = 22.
// Since after further breaking we can not get maximum
// sum hence number is itself maximum i.e; answer is 23
Una solución simple para este problema es hacerlo recursivamente . En cada llamada tenemos que marcar solo max((max(n/2) + max(n/3) + max(n/4)), n) y devolverlo. Porque podemos obtener la suma máxima dividiendo el número en partes o el número es en sí mismo máximo. A continuación se muestra la implementación del algoritmo recursivo.
C++
// A simple recursive C++ program to find
// maximum sum by recursively breaking a
// number in 3 parts.
#include<bits/stdc++.h>
using namespace std;
// Function to find the maximum sum
int breakSum(int n)
{
// base conditions
if (n==0 || n == 1)
return n;
// recursively break the number and return
// what maximum you can get
return max((breakSum(n/2) + breakSum(n/3) +
breakSum(n/4)), n);
}
// Driver program to run the case
int main()
{
int n = 12;
cout << breakSum(n);
return 0;
}
Java
// A simple recursive JAVA program to find
// maximum sum by recursively breaking a
// number in 3 parts.
import java.io.*;
class GFG {
// Function to find the maximum sum
static int breakSum(int n)
{
// base conditions
if (n==0 || n == 1)
return n;
// recursively break the number and return
// what maximum you can get
return Math.max((breakSum(n/2) + breakSum(n/3) +
breakSum(n/4)), n);
}
// Driver program to test the above function
public static void main (String[] args) {
int n = 12;
System.out.println(breakSum(n));
}
}
// This code is contributed by Amit Kumar
Python3
# A simple recursive Python3 program to # find maximum sum by recursively breaking # a number in 3 parts. # Function to find the maximum sum def breakSum(n) : # base conditions if (n == 0 or n == 1) : return n # recursively break the number and # return what maximum you can get return max((breakSum(n // 2) + breakSum(n // 3) + breakSum(n // 4)), n) # Driver Code if __name__ == "__main__" : n = 12 print(breakSum(n)) # This code is contributed by Ryuga
C#
// A simple recursive C# program to find
// maximum sum by recursively breaking a
// number in 3 parts.
using System;
class GFG {
// Function to find the maximum sum
static int breakSum(int n)
{
// base conditions
if (n==0 || n == 1)
return n;
// recursively break the number
// and return what maximum you
// can get
return Math.Max((breakSum(n/2)
+ breakSum(n/3)
+ breakSum(n/4)), n);
}
// Driver program to test the
// above function
public static void Main ()
{
int n = 12;
Console.WriteLine(breakSum(n));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// A simple recursive PHP program to find
// maximum sum by recursively breaking a
// number in 3 parts.
// Function to find the maximum sum
function breakSum($n)
{
// base conditions
if ($n == 0 || $n == 1)
return $n;
// recursively break the number and
// return what maximum you can get
return max((breakSum(intval($n / 2)) +
breakSum(intval($n / 3)) +
breakSum(intval($n / 4))), $n);
}
// Driver program to run the case
$n = 12;
echo breakSum($n);
// This code is contributed by ita_c
?>
Javascript
<script>
// A simple recursive Javascript program to find
// maximum sum by recursively breaking a
// number in 3 parts.
// Function to find the maximum sum
function breakSum(n)
{
// base conditions
if (n==0 || n == 1)
return n;
// recursively break the number and return
// what maximum you can get
return Math.max((breakSum(Math.floor(n/2)) +
breakSum(Math.floor(n/3)) +
breakSum(Math.floor(n/4))), n);
}
// Driver program to test the above function
let n = 12;
document.write(breakSum(n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción :
13
Una solución eficiente para este problema es usar la programación Dinámica porque al dividir el número en partes recursivamente tenemos que realizar algunos problemas de superposición. Por ejemplo, parte de n = 30 será {15,10,7} y parte de 15 será {7,5,3}, por lo que tenemos que repetir el proceso para 7 dos veces para romper más. Para evitar este problema de superposición, estamos utilizando la programación dinámica . Almacenamos valores en una array y si para cualquier número en llamadas recursivas ya tenemos una solución para ese número actualmente, lo extraemos directamente de la array.
C++
// A Dynamic programming based C++ program
// to find maximum sum by recursively breaking
// a number in 3 parts.
#include<bits/stdc++.h>
#define MAX 1000000
using namespace std;
int breakSum(int n)
{
int dp[n+1];
// base conditions
dp[0] = 0, dp[1] = 1;
// Fill in bottom-up manner using recursive
// formula.
for (int i=2; i<=n; i++)
dp[i] = max(dp[i/2] + dp[i/3] + dp[i/4], i);
return dp[n];
}
// Driver program to run the case
int main()
{
int n = 24;
cout << breakSum(n);
return 0;
}
Java
// A simple recursive JAVA program to find
// maximum sum by recursively breaking a
// number in 3 parts.
import java.io.*;
class GFG {
final int MAX = 1000000;
// Function to find the maximum sum
static int breakSum(int n)
{
int dp[] = new int[n+1];
// base conditions
dp[0] = 0; dp[1] = 1;
// Fill in bottom-up manner using recursive
// formula.
for (int i=2; i<=n; i++)
dp[i] = Math.max(dp[i/2] + dp[i/3] + dp[i/4], i);
return dp[n];
}
// Driver program to test the above function
public static void main (String[] args) {
int n = 24;
System.out.println(breakSum(n));
}
}
// This code is contributed by Amit Kumar
Python3
# A Dynamic programming based Python program # to find maximum sum by recursively breaking # a number in 3 parts. MAX = 1000000 def breakSum(n): dp = [0]*(n+1) # base conditions dp[0] = 0 dp[1] = 1 # Fill in bottom-up manner using recursive # formula. for i in range(2, n+1): dp[i] = max(dp[int(i/2)] + dp[int(i/3)] + dp[int(i/4)], i); return dp[n] # Driver program to run the case n = 24 print(breakSum(n)) # This code is contributed by # Smitha Dinesh Semwal
C#
// A simple recursive C# program to find
// maximum sum by recursively breaking a
// number in 3 parts.
using System;
class GFG {
// Function to find the maximum sum
static int breakSum(int n)
{
int []dp = new int[n+1];
// base conditions
dp[0] = 0; dp[1] = 1;
// Fill in bottom-up manner
// using recursive formula.
for (int i = 2; i <= n; i++)
dp[i] = Math.Max(dp[i/2] +
dp[i/3] + dp[i/4], i);
return dp[n];
}
// Driver program to test the
// above function
public static void Main ()
{
int n = 24;
Console.WriteLine(breakSum(n));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// A Dynamic programming based PHP program
// to find maximum sum by recursively breaking
// a number in 3 parts.
function breakSum($n)
{
$dp = array_fill(0, $n + 1, 0);
// base conditions
$dp[0] = 0;
$dp[1] = 1;
// Fill in bottom-up manner using
// recursive formula.
for ($i = 2; $i <= $n; $i++)
$dp[$i] = max($dp[(int)($i / 2)] +
$dp[(int)($i / 3)] +
$dp[(int)($i / 4)], $i);
return $dp[$n];
}
// Driver Code
$n = 24;
echo breakSum($n);
// This code is contributed by mits
?>
Javascript
<script>
// A simple recursive JAVASCRIPT program to find
// maximum sum by recursively breaking a
// number in 3 parts.
let MAX = 1000000;
// Function to find the maximum sum
function breakSum(n)
{
let dp=new Array(n+1);
for(let i=0;i<dp;i++)
{
dp[i]=0;
}
// base conditions
dp[0] = 0; dp[1] = 1;
// Fill in bottom-up manner using recursive
// formula.
for (let i=2; i<=n; i++)
dp[i] = Math.max(dp[Math.floor(i/2)] +
dp[Math.floor(i/3)] + dp[Math.floor(i/4)], i);
return dp[n];
}
// Driver program to test the above function
let n = 24;
document.write(breakSum(n));
// This code is contributed by rag2127
</script>
Producción:
27
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA