# Greatest Sum Divisible by Three
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/greatest-sum-divisible-by-three)
Canonical: https://scaleengineer.com/dsa/problems/greatest-sum-divisible-by-three
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
Given an integer array `nums`, return _the **maximum possible sum** of elements of the array such that it is divisible by three_.

**Example 1:**

**Input:** nums = [3,6,5,1,8]
**Output:** 18
**Explanation:** Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

**Example 2:**

**Input:** nums = [4]
**Output:** 0
**Explanation:** Since 4 is not divisible by 3, do not pick any number.

**Example 3:**

**Input:** nums = [1,2,3,4,4]
**Output:** 12
**Explanation:** Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

**Constraints:**

* `1 <= nums.length <= 4 * 104`
* `1 <= nums[i] <= 104`

# Approaches
## Brute Force using Backtracking
This approach explores all possible subsets of the `nums` array using recursion (backtracking). For each subset, it calculates the sum of its elements. If the sum is divisible by three, it is compared with the maximum sum found so far. This method guarantees finding the correct answer by checking every possibility, but it is highly inefficient.
**Time:** O(2^N), where N is the number of elements in `nums`. For each element, we have two choices (include or exclude), leading to `2^N` possible subsets to check. · **Space:** O(N), where N is the number of elements in `nums`. This space is used by the recursion stack.
**Pros:** Simple to understand and implement the logic.; Guaranteed to find the correct solution by exploring all possibilities.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
### Explanation
We can implement this using a recursive helper function, say `solve(index, currentSum)`. The function explores two branches at each step: one where the current number `nums[index]` is included in the sum, and one where it's excluded. The base case for the recursion is when we have considered all numbers (i.e., `index` reaches the end of the array). At this point, we check if the `currentSum` is divisible by 3. If it is, we update our global maximum answer. The initial call would be `solve(0, 0)`.

```java
class Solution {
    int maxSum = 0;

    public int maxSumDivThree(int[] nums) {
        solve(0, 0, nums);
        return maxSum;
    }

    private void solve(int index, int currentSum, int[] nums) {
        if (index == nums.length) {
            if (currentSum % 3 == 0) {
                maxSum = Math.max(maxSum, currentSum);
            }
            return;
        }

        // Option 1: Include nums[index]
        solve(index + 1, currentSum + nums[index], nums);

        // Option 2: Exclude nums[index]
        solve(index + 1, currentSum, nums);
    }
}
```
### Algorithm
- Initialize a global variable `maxSum = 0`.
- Define a recursive function `solve(index, currentSum)`.
- **Base Case:** If `index` reaches the end of the array (`nums.length`):
  - Check if `currentSum` is divisible by 3.
  - If it is, update `maxSum = max(maxSum, currentSum)`.
  - Return from the function.
- **Recursive Step:** For the element at the current `index`:
  - Make a recursive call including the element: `solve(index + 1, currentSum + nums[index])`.
  - Make another recursive call excluding the element: `solve(index + 1, currentSum)`.
- Start the process by calling `solve(0, 0)`.
- After the recursion completes, return `maxSum`.

## Dynamic Programming
This approach uses dynamic programming to efficiently solve the problem. We maintain an array that keeps track of the maximum sum achievable for each possible remainder modulo 3 (0, 1, and 2). We iterate through the numbers in the input array and update these maximum sums at each step. This avoids redundant calculations and provides a linear time solution.
**Time:** O(N), where N is the number of elements in `nums`. We iterate through the array once, and for each element, we perform a constant number of operations. · **Space:** O(1), as we only use a constant amount of extra space for the `dp` array of size 3.
**Pros:** Highly efficient with linear time complexity.; Uses constant extra space, making it suitable for large inputs.; It's a standard DP pattern that can be applied to similar problems.
**Cons:** The state transition logic might be slightly less intuitive to grasp initially compared to a direct mathematical formula.
### Explanation
We use an array, `dp`, of size 3. `dp[i]` will store the largest sum we can form that has a remainder of `i` when divided by 3. We initialize `dp` as `[0, 0, 0]`.

We iterate through each number `num` in the `nums` array. For each `num`, we calculate the potential new sums by adding `num` to the existing sums stored in `dp`. To ensure that we use the sums from the previous step for our calculations, we create a temporary copy of the `dp` array before performing updates for the current `num`.

For each of the three possible previous sums (for remainders 0, 1, and 2), we add the current `num`, find the new remainder, and update the corresponding entry in our main `dp` array if the new sum is larger. After processing all numbers, `dp[0]` will contain the maximum sum that is divisible by 3.

```java
class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] dp = new int[3];
        // dp[0] = max sum with remainder 0
        // dp[1] = max sum with remainder 1
        // dp[2] = max sum with remainder 2
        
        for (int num : nums) {
            int[] tempDp = new int[3];
            tempDp[0] = dp[0];
            tempDp[1] = dp[1];
            tempDp[2] = dp[2];

            for (int prevSum : tempDp) {
                int currentSum = prevSum + num;
                int remainder = currentSum % 3;
                dp[remainder] = Math.max(dp[remainder], currentSum);
            }
        }
        
        return dp[0];
    }
}
```
### Algorithm
- Initialize a DP array `dp` of size 3, where `dp[i]` will store the maximum sum found so far that has a remainder of `i` when divided by 3. Initialize `dp = [0, 0, 0]`.
- Iterate through each number `num` in the input array `nums`.
- Inside the loop, create a temporary copy of the `dp` array, let's call it `tempDp`.
- For each `prevSum` in `tempDp`:
  - Calculate the `newSum = prevSum + num`.
  - Find the remainder of the new sum: `rem = newSum % 3`.
  - Update the `dp` array: `dp[rem] = Math.max(dp[rem], newSum)`.
- After iterating through all numbers, the value `dp[0]` will hold the maximum possible sum that is divisible by 3.
- Return `dp[0]`.

## Greedy Mathematical Approach
This is the most optimal approach, based on a mathematical insight. The idea is to first calculate the sum of all numbers. If this sum is already divisible by 3, it's our answer. If not, we must remove some numbers to make the sum divisible by 3. To maximize the final sum, we should remove the number or combination of numbers with the smallest possible sum that corrects the remainder. This can be done in a single pass.
**Time:** O(N), as we iterate through the `nums` array only once to compute the sum and find the smallest required numbers. · **Space:** O(1), as we only use a few variables to store the total sum and the smallest numbers, regardless of the input size.
**Pros:** The most efficient solution with O(N) time and O(1) space.; The logic is direct and based on a clear mathematical property, potentially leading to faster execution due to fewer operations per element compared to the DP approach.
**Cons:** The logic requires careful handling of edge cases, such as when the required numbers for removal do not exist in the array.
### Explanation
First, we calculate the total sum of all elements in `nums`. Let this be `totalSum`. The core idea depends on `totalSum % 3`:

- **If `totalSum % 3 == 0`**: The sum is already perfect. The answer is `totalSum`.
- **If `totalSum % 3 == 1`**: We need to remove a sub-sum that is `1 mod 3`. To get the largest remaining sum, we must remove the smallest possible value. The options are:
  1. Remove the single smallest number where `num % 3 == 1`.
  2. Remove the two smallest numbers where `num % 3 == 2` (since `(2 + 2) % 3 = 1`).
- **If `totalSum % 3 == 2`**: We need to remove a sub-sum that is `2 mod 3`. The options are:
  1. Remove the single smallest number where `num % 3 == 2`.
  2. Remove the two smallest numbers where `num % 3 == 1` (since `(1 + 1) % 3 = 2`).

We can find the `totalSum` and the necessary smallest numbers (two with remainder 1, two with remainder 2) in a single pass through the array. Then, we apply the logic above to find the maximum possible sum.

```java
class Solution {
    public int maxSumDivThree(int[] nums) {
        int totalSum = 0;
        int min1_rem1 = Integer.MAX_VALUE, min2_rem1 = Integer.MAX_VALUE;
        int min1_rem2 = Integer.MAX_VALUE, min2_rem2 = Integer.MAX_VALUE;

        for (int num : nums) {
            totalSum += num;
            if (num % 3 == 1) {
                if (num < min1_rem1) {
                    min2_rem1 = min1_rem1;
                    min1_rem1 = num;
                } else if (num < min2_rem1) {
                    min2_rem1 = num;
                }
            } else if (num % 3 == 2) {
                if (num < min1_rem2) {
                    min2_rem2 = min1_rem2;
                    min1_rem2 = num;
                } else if (num < min2_rem2) {
                    min2_rem2 = num;
                }
            }
        }

        int rem = totalSum % 3;

        if (rem == 0) {
            return totalSum;
        }

        int ans = 0;
        if (rem == 1) {
            if (min1_rem1 != Integer.MAX_VALUE) {
                ans = Math.max(ans, totalSum - min1_rem1);
            }
            if (min2_rem2 != Integer.MAX_VALUE) {
                ans = Math.max(ans, totalSum - min1_rem2 - min2_rem2);
            }
        } else { // rem == 2
            if (min1_rem2 != Integer.MAX_VALUE) {
                ans = Math.max(ans, totalSum - min1_rem2);
            }
            if (min2_rem1 != Integer.MAX_VALUE) {
                ans = Math.max(ans, totalSum - min1_rem1 - min2_rem1);
            }
        }

        return ans;
    }
}
```
### Algorithm
- Initialize `totalSum = 0`.
- Initialize variables to track the two smallest numbers with remainder 1 (`min1_rem1`, `min2_rem1`) and remainder 2 (`min1_rem2`, `min2_rem2`). Set them to a value larger than any possible input, like `Integer.MAX_VALUE`.
- Iterate through `num` in `nums`:
  - Add `num` to `totalSum`.
  - If `num % 3 == 1`, update the two smallest remainder-1 numbers.
  - If `num % 3 == 2`, update the two smallest remainder-2 numbers.
- Calculate the remainder of the total sum: `rem = totalSum % 3`.
- If `rem == 0`, return `totalSum`.
- If `rem == 1`:
  - Calculate the sum after removing the smallest remainder-1 number.
  - Calculate the sum after removing the two smallest remainder-2 numbers.
  - Return the maximum of these two options. If neither removal is possible, the answer is 0.
- If `rem == 2`:
  - Calculate the sum after removing the smallest remainder-2 number.
  - Calculate the sum after removing the two smallest remainder-1 numbers.
  - Return the maximum of these two options. If neither removal is possible, the answer is 0.

# Solutions
### Java

```java
class Solution { public int maxSumDivThree ( int [] nums ) { int n = nums . length ; final int inf = 1 << 30 ; int [][] f = new int [ n + 1 ][ 3 ]; f [ 0 ][ 1 ] = f [ 0 ][ 2 ] = - inf ; for ( int i = 1 ; i <= n ; ++ i ) { int x = nums [ i - 1 ]; for ( int j = 0 ; j < 3 ; ++ j ) { f [ i ][ j ] = Math . max ( f [ i - 1 ][ j ], f [ i - 1 ][( j - x % 3 + 3 ) % 3 ] + x ); } } return f [ n ][ 0 ]; } }
```

### CPP

```cpp
class Solution { public: int maxSumDivThree ( vector < int >& nums ) { int n = nums . size (); const int inf = 1 << 30 ; int f [ n + 1 ][ 3 ]; f [ 0 ][ 0 ] = 0 ; f [ 0 ][ 1 ] = f [ 0 ][ 2 ] = - inf ; for ( int i = 1 ; i <= n ; ++ i ) { int x = nums [ i - 1 ]; for ( int j = 0 ; j < 3 ; ++ j ) { f [ i ][ j ] = max ( f [ i - 1 ][ j ], f [ i - 1 ][( j - x % 3 + 3 ) % 3 ] + x ); } } return f [ n ][ 0 ]; } };
```

### Python

```python
class Solution : def maxSumDivThree ( self , nums : List [ int ]) -> int : n = len ( nums ) f = [[ - inf ] * 3 for _ in range ( n + 1 )] f [ 0 ][ 0 ] = 0 for i , x in enumerate ( nums , 1 ): for j in range ( 3 ): f [ i ][ j ] = max ( f [ i - 1 ][ j ], f [ i - 1 ][( j - x ) % 3 ] + x ) return f [ n ][ 0 ]
```