최대 합계 문제 GeeksForGeeks

Input:
n = 12
Output: 13
Explanation: Break n = 12 in three parts
{12/2, 12/3, 12/4} = {6, 4, 3}, now current
sum is = (6 + 4 + 3) = 13. Further breaking 6,
4 and 3 into parts will produce sum less than
or equal to 6, 4 and 3 respectively.

//User function Template for Java 
//recursive solution tc : o(3^n) as we are calling recursive function 3 times /2,/3 and /4
//space time complexity is : o(3^n) auxillary space for the stack as their will be 
// 3^n stack space that will be required
/*
class Solution
{
    public int maxSum(int n) 
    { 
        return solve(n);
    } 
    public int solve(int n){
        if(n==1 || n==0) return n;

        int a = n/2;
        int b = n/3;
        int c = n/4;

        return Integer.max(n,
        solve(a)+solve(b)+solve(c)
        );
    }
} */
// optimized solution using dynamic programming memoization top down approach
// time complexity is O(n) as at max there will be n states and dp will traverse those states 
// space complexity will be O(n) for dp and o(n) for stack space;
class Solution
{
    public int maxSum(int n) 
    { 
        int dp[] = new int[1000001];
        Arrays.fill(dp,-1);
        return solve(n,dp);
    } 
    public int solve(int n,int dp[]){
        if(n==1 || n==0) return n;
        if(dp[n]!=-1) return dp[n];
        int a = n/2;
        int b = n/3;
        int c = n/4;

        return dp[n]= Integer.max(n,
        solve(a,dp)+solve(b,dp)+solve(c,dp)
        );
    }
}