#1262

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Greatest Sum Divisible by Three

Find the maximum sum divisible by three from a given array using dynamic programming and state transition.

array dynamic programming greedy sorting

Problem Statement

Given an integer array nums, return the maximum possible sum of the elements such that the sum is divisible by three. If no such sum exists, return 0.

You must maximize the sum while ensuring that the sum modulo three equals zero. Use dynamic programming with a state transition approach to solve the problem efficiently.

Examples

Example 1

Input: nums = [3,6,5,1,8]

Output: 18

Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2

Input: nums = [4]

Output: 0

Since 4 is not divisible by 3, do not pick any number.

Example 3

Input: nums = [1,2,3,4,4]

Output: 12

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 Approach

State Transition Dynamic Programming

Represent the state as DP[pos][mod], where pos refers to the current index in the array and mod is the current sum modulo 3. For each number in the array, update the states and track the maximum sum that is divisible by three.

Greedy and Sorting Optimization

In certain cases, sorting the array and greedily selecting numbers based on their modulo 3 values can provide quick insights into which numbers contribute to the maximum sum divisible by three.

Iterative State Updates

Iterate through the array, updating possible states at each step, ensuring that the sum modulo 3 is adjusted based on the current number. This ensures that the dynamic programming state transitions are efficiently managed.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the chosen dynamic programming approach, typically O(n) or O(n * 3) for state transitions, where n is the length of the input array. Space complexity can be O(3) or O(n * 3), depending on the representation of states.

What Interviewers Usually Probe

Ability to recognize state transition patterns in dynamic programming.
Understanding of greedy techniques for optimizing the sum.
Comfort with handling arrays and ensuring the sum is divisible by three.

Common Pitfalls or Variants

Common pitfalls

Not properly managing the modulo 3 states during dynamic programming updates.
Confusing the maximum sum with the largest number divisible by three.
Incorrectly handling edge cases where no sum is divisible by three.

Follow-up variants

Modify the problem to find the minimum sum divisible by three.
Extend the problem to include negative integers in the array.
Apply this approach to a multidimensional array for greater complexity.

FAQ

What is the approach for solving the Greatest Sum Divisible by Three?

The solution uses dynamic programming with state transitions, represented as DP[pos][mod], to track the maximum possible sum divisible by three.

How can I optimize this problem using greedy algorithms?

Sorting the array based on modulo 3 values and selecting numbers greedily can optimize the solution, though dynamic programming is the most efficient method.

What is the time complexity of the solution?

The time complexity depends on the approach, usually O(n) or O(n * 3), where n is the length of the array.

Can this approach be extended to multidimensional arrays?

Yes, the state transition dynamic programming approach can be adapted for multidimensional arrays, increasing the problem's complexity.

What should I consider when implementing the solution?

Ensure that you correctly manage the modulo 3 states and handle edge cases where no sum is divisible by three.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the maximum sum of several numbers selected from the first $i$ numbers, such that the sum modulo $3$ equals $j$. Initially, $f[0][0]=0$, and the rest are $-\infty$.

1

2

3

4

5

6

7

8

9

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[-inf] * 3 for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(3):
                f[i][j] = max(f[i - 1][j], f[i - 1][(j - x) % 3] + x)
        return f[n][0]

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[-inf] * 3 for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(3):
                f[i][j] = max(f[i - 1][j], f[i - 1][(j - x) % 3] + x)
        return f[n][0]

Continue Practicing

#1363 largest multiple of three #646 maximum length of pair chain #435 non overlapping intervals