MediumNo. 1262

Greatest Sum Divisible by Three — LeetCode 1262 Python Solution

Pattern
Greedy
Topics
Greedy, Array, Dynamic Programming, Sorting
Reading time
2 min

The problem

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

Example

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).

Python solution

PythonSolution
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]

Complexity

Time
O(n)
Space · auxiliary
O(n)

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1262. Greatest Sum Divisible by Three is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0435Non-overlapping IntervalsMedium
0646Maximum Length of Pair ChainMedium
1363Largest Multiple of ThreeHard
1402Reducing DishesHard
2708Maximum Strength of a GroupMedium
0045Jump Game IIMedium

Frequently asked questions

How hard is LeetCode 1262. Greatest Sum Divisible by Three?

LeetCode 1262. Greatest Sum Divisible by Three is rated Medium on LeetCode.

What is the time complexity of LeetCode 1262. Greatest Sum Divisible by Three?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1262. Greatest Sum Divisible by Three?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1262. Greatest Sum Divisible by Three cover?

LeetCode 1262. Greatest Sum Divisible by Three is tagged Greedy, Array, Dynamic Programming and Sorting on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.