Maximum value with the choice of either dividing or considering as it is
We are given a number n, we need to find the maximum sum possible with the help of following function:
F(n) = max( (F(n/2) + F(n/3) + F(n/4) + F(n/5)), n). To calculate F(n, ) we may either have n as our result or we can further break n into four part as in given function definition. This can be done as much time as we can. Find the maximum possible sum you can get from a given N. Note : 1 can not be break further so F(1) = 1 as a base case.
Examples :
Input : n = 10 Output : MaxSum = 12 Explanation: f(10) = f(10/2) + f(10/3) + f(10/4) + f(10/5) = f(5) + f(3) + f(2) + f(2) = 12 5, 3 and 2 cannot be further divided. Input : n = 2 Output : MaxSum = 2
Approach : This problem can be solve with recursive approach but that will cost us a high complexity because of its overlapping sub problems. So we apply dynamic programming concept to solve this question in bottom up manner as:
C++
// CPP program for maximize result when // we have choice to divide or consider // as it is. #include <bits/stdc++.h> using namespace std; // function for calculating max possible result int maxDP( int n) { int res[n + 1]; res[0] = 0; res[1] = 1; // Compute remaining values in bottom // up manner. for ( int i = 2; i <= n; i++) res[i] = max(i, (res[i / 2] + res[i / 3] + res[i / 4] + res[i / 5])); return res[n]; } // Driver Code int main() { int n = 60; cout << "MaxSum =" << maxDP(n); return 0; } |
Java
// Java program for maximize result when // we have choice to divide or consider // as it is. import java.io.*; class GFG { // function for calculating max // possible result static int maxDP( int n) { int res[] = new int [n + 1 ]; res[ 0 ] = 0 ; res[ 1 ] = 1 ; // Compute remaining values in // bottom up manner. for ( int i = 2 ; i <= n; i++) res[i] = Math.max(i, (res[i / 2 ] + res[i / 3 ] + res[i / 4 ] + res[i / 5 ])); return res[n]; } // Driver Code public static void main(String[] args) { int n = 60 ; System.out.println( "MaxSum = " + maxDP(n)); } } // This code is contributed by vt_m |
Python3
# Python3 code to maximize result when # we have choice to divide or consider # as it is. # function for calculating max # possible result def maxDP (n): res = list () res.append( 0 ) res.append( 1 ) # Compute remaining values in # bottom up manner. i = 2 while i<n + 1 : res.append( max (i, (res[ int (i / 2 )] + res[ int (i / 3 )] + res[ int (i / 4 )] + res[ int (i / 5 )]))) i = i + 1 return res[n] # driver code n = 60 print ( "MaxSum =" , maxDP(n)) # This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program for maximize result when // we have choice to divide or consider // as it is. using System; class GFG { // function for calculating max // possible result static int maxDP( int n) { int [] res = new int [n + 1]; res[0] = 0; res[1] = 1; // Compute remaining values in // bottom up manner. for ( int i = 2; i <= n; i++) res[i] = Math.Max(i, (res[i / 2] + res[i / 3] + res[i / 4] + res[i / 5])); return res[n]; } // Driver code public static void Main() { int n = 60; Console.WriteLine( "MaxSum = " + maxDP(n)); } } // This code is contributed by vt_m |
PHP
<?php // PHP program to maximize // result when we have choice // to divide or consider as it is. // function for calculating // max possible result function maxDP ( $n ) { $res [0] = 0; $res [1] = 1; // Compute remaining values // in bottom up manner. for ( $i = 2; $i <= $n ; $i ++) $res [ $i ] = max( $i , ( $res [ $i / 2] + $res [ $i / 3] + $res [ $i / 4] + $res [ $i / 5])); return $res [ $n ]; } // Driver Code $n = 60; echo "MaxSum =" , maxDP ( $n ); // This code is contributed by aj_36 ?> |
Javascript
<script> // javascript program for maximize result when // we have choice to divide or consider // as it is. // function for calculating max // possible result function maxDP(n) { let res = []; res[0] = 0; res[1] = 1; // Compute remaining values in // bottom up manner. for (let i = 2; i <= n; i++){ res[i] = Math.max(i, (res[(Math.floor(i / 2))] + res[(Math.floor(i / 3))] + res[(Math.floor(i / 4))] + res[(Math.floor(i / 5))])); } return res[n]; } // Driver code let n = 60; document.write( "MaxSum = " + maxDP(n)); </script> |
Output
MaxSum =106
Time Complexity: O(N)
Auxiliary Space: O(N)