Introduction
This blog finds the maximum sum from the array such that the sum is divisible by three.
Problem Statement
You are given an array arr[] of length n contains integers, we need to find out the maximum possible sum of elements of the array such that it is divisible by three i.e you have to pick elements from an array whose sum is divisible by three and also sum is maximum.
Let's take some examples to understand this problem better.
Sample Examples
Example 1:
Given Array arr[] = {1,2,3,4,4}
Output  12
Explanation: Pick the numbers 1,3,4, and 4 whose sum is 12 and the sum is divisible by three.
Example 2:
Given Array arr[ ] = {3,3,3,1,2}
Output  12
Explanation: We can pick all elements sum is 12 and divisible by three.
Example 3:
Given Array arr[ ] = {4}
Output  0
Explanation: We cannot pick any element because 4 is not divisible by three.
Approach
The problem can easily be solved with dynamic programming. Lets first define our dynamic programing state dp[i][j], which stores the maximum sum that we can get using the first ‘i’ elements of the array and has remainder ‘j’, here we need sums divisible by 3 so j will be 0, 1, and 2.
why do we need all 3 values?
Let’s say we have the number 8 at ith index. 8 % 3 = 2
8 is not divisible by 3 and has remainder 2. so if we add 8 to the sum which has remainder 1
and these 2 will make a new sum which will be divisible by 3.
To handle cases like this, we need all three states in our dynamic programming.
The basic idea is as follows:

If let’s say we are at index ‘i’, and arr[i] % 3 = 2, then we do the following things,
 arr[i] can be added with the dp[i1][0] and this new sum will have remainder 2, so we will update dp[i][2].
 arr[i] can be added with the dp[i1][1] and this new sum will have a remainder of 0, so we will update dp[i][0].

arr[i] can be added with the dp[i1][2] and this new sum will have remainder 1, so we will update dp[i][1].

If let’s say we are at index ‘i’, and arr[i] % 3 = 1, then we do the following things,
 arr[i] can be added with the dp[i1][0] and this new sum will have remainder 1, so we will update dp[i][1].
 arr[i] can be added with the dp[i1][1] and this new sum will have a remainder of 2, so we will update dp[i][2].

arr[i] can be added with the dp[i1][2] and this new sum will have remainder 0, so we will update dp[i][0].

If let’s say we are at index ‘i’, and arr[i] % 3 = 0, then we do the following things,
 arr[i] can be added with the dp[i1][0] and this new sum will have remainder 0, so we will update dp[i][0].
 arr[i] can be added with the dp[i1][1] and this new sum will have a remainder of 1, so we will update dp[i][1].
 arr[i] can be added with the dp[i1][2] and this new sum will have remainder 2, so we will update dp[i][2].
Note: if dp[i1][j] is zero then the other two sums will be considered only if they are greater than 0