1262. Greatest Sum Divisible by Three

Given an array nums of integers, we need to find 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:

---

Intuition

When a number is divided by 3, there are 3 possible remainders

0 => Exact multiple

If we track max sum for each remainder => ans = sum with remainder 0

Algo

Init - size 3 array with size 0 - max with remainders 0, 1, 2

Add current number to each sum, find the remainder => index in the sums array

Update sums array with new max for that remainder

Init the next array to sums array on each iteration => next = sums.clone()

---

Time - O(N)

Space - O(1)

---

	class Solution {
	public int maxSumDivThree(int[] nums) {
	int[] sums = new int[3];

	for (int num: nums) {
	int[] next = sums.clone();

	for (int i = 0; i < 3; i++) {
	int sum = sums[i] + num;
	int index = sum % 3;

	next[index] = Math.max(sum, next[index]);
	}

	sums = next;
	}

	return sums[0];
	}
	}

	class Solution {
	public int maxSumDivThree(int[] nums) {
	return dfs(nums, 0, 0);
	}

	private int dfs(int[] nums, int i, int sum) {
	// Termination => Return sum if multiple of 3 else return 0
	if (i == nums.length) {
	return sum % 3 == 0 ? sum : 0;
	}

	int ans = 0;

	// At current index, either participate in sum, or don't, return max
	ans = Math.max(dfs(nums, i + 1, sum + nums[i]), dfs(nums, i + 1, sum));

	return ans;
	}
	}

SWE Interview preparation