1262. Greatest Sum Divisible by Three

-

https://leetcode.com/problems/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:

    • 1 <= nums.length <= 4 * 10^4
    • 1 <= nums[i] <= 10^4
    ---
    Intuition

    When a number is divided by 3,  there are 3 possible remainders
    0 => Exact multiple
    1
    2

    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)
    ---