1262. Greatest Sum Divisible by Three¶
题目信息¶
- 题号:
1262
- 难度:
Medium
- 主题:
数组、动态规划、模三状态
- 原题:
- 重点:
从数组中选择任意子集,使元素和能被
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 整除。