# Greatest Sum Divisible by Three LeetCode Solution

DeShaw ShopeeViews 73

## Problem Statement:

Greatest Sum Divisible by Three LeetCode Solution:  Array `nums` of integers are given, 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`

## Approach:

1. This problem can be solved by using Dynamic Programming
2. Every number can be represented as a reminder of  3. So, num% 3 can be 0,1,2.
3. Our dp state is represented by rec(ind, sum).
4. rec(ind,0) = largest sum till index is divided by three.
5. rec(ind,1)=  largest sum when divided by 3, remainder = 1.
6. rec(ind,2)=  largest sum when divided by 3, remainder = 2.
7. We will use include exclude principal to tackle this dp.
8. rec(ind,sum)=max(a[ind]+rec(ind,(sum+a[ind])%3),rec(ind+1,sum)).
9. Now discuss the base condition. If we reach the end of the array then (reminder of a sum) must be zero.
10. We will discuss recursion with memoization.

## Code of Greatest Sum Divisible by Three LeetCode Solution:

### C++ Code:

```class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
vector<int> dp={0,INT_MIN,INT_MIN};

for(auto i: nums){
vector<int> tmp(3);

for(int j=0;j<3;j++){
tmp[(j+i)%3]=max(dp[(j+i)%3],dp[j]+i);
}

dp=tmp;
}

return dp[0];
}
};```

### Java Code:

```class Solution {
int[][] dp = new int[100005][3];
int n;
int rec(int ind,int sum,int[] a)
{
if(ind>=n)
{
if(sum!=0)
return Integer.MIN_VALUE;
return 0;
}
if(dp[ind][sum]!=-1)
return dp[ind][sum];
int k=(sum+a[ind])%3;
int ans1=a[ind]+rec(ind+1,k,a);
int ans2=rec(ind+1,sum,a);
return dp[ind][sum]=Math.max(ans1,ans2);
}

public int maxSumDivThree(int[] nums) {
n=nums.length;
int i,j;
for(i=0;i<=n;i++)
for(j=0;j<=2;j++)
dp[i][j]=-1;
return rec(0,0,nums);
}
}

```

## Complexity Analysis for Greatest Sum Divisible by Three LeetCode Solution:

### Time complexity:

Time complexity is o(n*3) or we can simply say o(n).

### Space complexity:

Space complexity is o(n*3) or we can simply say o(n). We are creating a dp table to store the values.

Translate »