1262. Greatest Sum Divisible by Three

题目信息

题号:

1262

难度:

Medium

主题:

数组、动态规划、模三状态

原题:

LeetCode 1262

重点:

从数组中选择任意子集,使元素和能被 3 整除并最大化;允许选择空子集,和为 0

题目重述

给定正整数数组 nums。可以选择其中任意数量的元素,每个元素最多选择一次。

请返回所有元素和能被 3 整除的选择方案中,能够得到的最大总和。若不存在正和方案,可以选择空子集并返回 0。

1 <= nums.length <= 4 * 10^4,1 <= nums[i] <= 10^4。

自建示例

舍弃一个余数不合适的元素可得到最大和:

输入:nums = [4,1,5,3]
输出:12
解释:选择 4、5、3,总和为 12;全部元素之和 13 不能被 3 整除。

没有非空子集满足条件时返回零:

输入:nums = [1,1]
输出:0
解释:可得到的正和为 1 或 2,都不能被 3 整除。