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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.