Leetcode 1262. Greatest Sum Divisible by Three

Problem Explanation

You are given an array of integers, and the task is to find the maximum possible sum of elements in the array that is divisible by three. Essentially, you have to pick out some numbers from the array so that their sum is the largest possible which can be divided evenly by three. If no such combination can be found, the output should be zero.

It's important to note that you don't necessarily have to use all the elements in the array. You can leave out some numbers if including them would result in a sum that isn't divisible by three.

For example, given the array [3,6,5,1,8], we can pick the numbers [3,6,1,8]. The sum of these numbers is 18, which is the maximum sum we can achieve that is divisible by three.

Solution Approach

The problem can be solved by using dynamic programming.

The main idea is to maintain a dynamic programming array dp. Each element in dp represents the maximum sum we can get given the current remainder when divided by 3. For example, dp[0] stores the maximum sum which is divisible by three, dp[1] stores the maximum sum which has remainder 1 when divided by three, and so on.

We iterate over each number in the input array, and for each number, we also loop over each element in dp. The value of dp is updated based on the current number and the value stored in dp.

After going through all numbers in the array, the value of dp[0] will be the maximum sum that is divisible by three.

Python Solution

1
2python
3class Solution:
4    def maxSumDivThree(self, nums: List[int]) -> int:
5        dp = [0]*3  # Initialize dynamic programming array
6        for num in nums:
7            for i in list(dp):  # Create a copy of dp since we need to modify it in loop
8                dp[(i+num)%3] = max(dp[(i+num)%3], i+num)
9        return dp[0]

Java Solution

1
2java
3class Solution {
4    public int maxSumDivThree(int[] nums) {
5        int[] dp = new int[3];
6        for (int num : nums) {
7            int[] temp = dp.clone();
8            for (int sum : temp) {
9                dp[(sum + num) % 3] = Math.max(dp[(sum + num) % 3], sum + num);
10            }
11        }
12        return dp[0];
13    }
14}

JavaScript Solution

1
2javascript
3var maxSumDivThree = function(nums) {
4    const dp = [0, 0, 0];
5    for (let num of nums) {
6        const temp = [...dp];
7        for (let sum of temp) {
8            dp[(sum+num)%3] = Math.max(dp[(sum+num)%3], sum+num);
9        }
10    }
11    return dp[0];
12};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int maxSumDivThree(vector<int>& nums) {
6        // Initialize dynamic programming array
7        vector<int> dp(3, 0);
8        for (const int& num : nums) {
9            // Create a copy of dp since we need to modify it in loop
10            vector<int> tmp_dp(dp.begin(), dp.end());
11            for (const int& sum : tmp_dp) {
12                dp[(sum + num) % 3] = max(dp[(sum + num) % 3], sum + num);
13            }
14        }
15        return dp[0];
16    }
17};

C# Solution

1
2csharp
3public class Solution {
4    public int MaxSumDivThree(int[] nums) {
5        int[] dp = new int[3];
6        foreach (int num in nums) {
7            int[] temp = (int[]) dp.Clone();
8            foreach (int sum in temp) {
9                dp[(sum + num) % 3] = Math.Max(dp[(sum + num) % 3], sum + num);
10            }
11        }
12        return dp[0];
13    }
14}

The solutions in different languages essentially do the same thing using the same approach, but the syntax and some built-in functions vary among different languages.## Problem implementation in Python, JS, Java, C++, and C#

These different coding languages essentially approach the problem in the same way. But, they differ in the syntax, usage of built-in functions and how they handle array variables.

Python

In Python, we make use of list comprehensions and the use of the max function which returns the largest item in an iterable. Here, for the dynamic programming array dp, we're taking the maximum of the existing value and the sum of the number in the input array and the current value in dp.

JavaScript

JavaScript makes use of the const keyword which declares a read-only named constant. Then Math.max is used to pick the maximum between the current value and the sum of the number in the input array and the current value in dp.

Java

In Java, we use the clone method for creating a copy of the dp array before modifying it. Also, Java uses Math.max function like JavaScript for picking the maximum.

C++

In C++, we make use of vector to maintain our dynamic programming array dp. Also, we are using max function that returns the largest of the two parameters.

C#

Same as Java and JavaScript, C# uses the Clone method to get a copy of array which further helps in calculating the maximum using Math.Max function.

Through this approach using dynamic programming, we are able to solve the problem in numerous languages. Though the syntax and built-in functions may differ, the basic thought behind the approach remains the same. Understanding the problem statement thoroughly and choosing the right approach will help in making implementation easier irrespective of the language.