1262. Greatest Sum Divisible by Three

Problem Link

Description

---

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

Solution

---

Python3

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0, 0, 0]
        
        for num in nums:
            
            for i in dp[:]:
                dp[(i+num)%3] = max(dp[(i+num)%3], num + i)
            
        
        return dp[0]
    

C++

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> dp {0,0,0}, dp2;
        
        for (int num : nums){
            dp2 = dp;
            
            for (int i : dp2){
                dp[(num+i)%3] = max(dp[(num+i)%3], num+i);
            }
        }
        
        return dp[0];
    }
};