Maximum Sum Problem

Time: O(n)

Space: O(n)

Intuition

The idea is: given a number n, you can either use it directly or "reduce" it by dividing into n/2, n/3, and n/4 (integer division). The goal is to maximize the sum. Recursively, you compute the best outcome for each sub-problem and memoize to avoid redundant calculations.

Algorithm

1Base case: if n == 0, return 0.
2Recursive case: return max(n, maxSum(n/2) + maxSum(n/3) + maxSum(n/4)).
3If memoization is available, check memo[n] before computing.
4Store result in memo[n] after computing.

Example Walkthrough

Input: n = 10

1.maxSum(10) = max(10, maxSum(5) + maxSum(3) + maxSum(2)).
2.maxSum(5) = max(5, maxSum(2) + maxSum(1) + maxSum(1)) = max(5, 4) = 5.
3.maxSum(3) = max(3, maxSum(1) + maxSum(1) + maxSum(0)) = max(3, 2) = 3.
4.maxSum(2) = max(2, maxSum(1) + maxSum(0) + maxSum(0)) = max(2, 1) = 2.
5.maxSum(1) = max(1, 0+0+0) = 1.
6.maxSum(10) = max(10, 5 + 3 + 2) = max(10, 10) = 10.

Output: 10

Common Pitfalls

•Integer division in recursion: n/2, n/3, n/4 are floor divisions; for n=5, n/4=1 and n/3=1.
•Without memoization, the same sub-problems are recomputed exponentially (e.g., maxSum(5) called multiple times).
•Base case matters: ensure n=0 returns 0, not negative or undefined.

Maximum Sum Problem.java

Java


// Approach: Recursion with memoization. maxSum(n) = max(n, maxSum(n/2) + maxSum(n/3) + maxSum(n/4)).
// At each step, choose to either take n directly or split into smaller pieces.
// Memoize results to avoid recomputation.
// Time: O(n) Space: O(n)

class Solution {

    public int maxSum(int n) {
        if (n == 0) {
            return 0;
        }
        return Math.max(n, (maxSum(n / 2) + maxSum(n / 3) + maxSum(n / 4)));
    }
}

Was this solution helpful?