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 = 60print("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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
