algorithm - 给定一个整数数组，使用数组的数字找到最大的数字，使其可以被 3 整除

Question

例如:Array: 4,3,0,1,5 {假设所有数字都 >=0。数组中的每个元素也对应一个数字。即数组中的每个元素都在 0 到 9 之间。

在上面的数组中，最大的数是:5430 {使用数组中的数字 5、4、3 和 0}

我的方法:

为了被 3 整除，我们需要数字之和能被 3 整除。所以，

1. 第 1 步:从数组中删除所有零。
2. 第 2 步:这些零将出现在最后。 {因为它们不影响总和，我们必须找到最大的数}
3. 第 3 步:找到数组元素的子集(不包括零)，使得数字的个数为 MAXIMUM，并且数字的总和为 MAXIMUM，并且总和可以被 3 整除。
4. 第 4 步:所需数字由上述搜索结果中的数字按降序排列组成。

因此，主要步骤是第 3 步，即 如何找到子集，使其包含最大可能数量的元素，使得它们的总和为 MAX 并且可以被 3 整除。

我在想，也许第 3 步可以通过贪婪选择来完成，即获取所有元素并继续删除集合中的最小元素，直到总和可以被 3 整除。

但我不相信这种贪婪的选择会奏效。

请问我的做法是否正确。如果是，那么请建议如何执行第 3 步？

此外，请提出任何其他可能/高效的算法。

Answer 1

观察:如果你能得到一个能被 3 整除的数字，你最多需要删除 2 个数字，以保持最优解。

一个简单的 O(n^2) 解决方案是检查所有可能性以删除 1 个数字，如果没有一个有效，则检查所有对(有 O(n^2 ) 的那些).

---

编辑:
O(n) 解决方案:创建 3 个桶 - bucket1、bucket2、bucket0。每个都表示数字的模数 3 值。在下一个算法中忽略bucket0。

令数组之和为sum。

If sum % 3 ==0: we are done.
else if sum % 3 == 1:
  if there is a number in bucket1 - chose the minimal
  else: take 2 minimals from bucket 2
else if sum % 3 == 2
  if there is a number in bucket2 - chose the minimal
  else: take 2 minimals from bucket1  

注意:您实际上并不需要桶，以实现 O(1) 空间 - 您只需要 bucket1 和 bucket2 中的 2 个最小值，因为它是我们实际使用的这些桶中的唯一数字。

示例:

arr = { 3, 4, 0, 1, 5 }
bucket0 = {3,0} ; bucket1 = {4,1} bucket2 = { 5 }
sum = 13 ; sum %3 = 1
bucket1 is not empty - chose minimal from it (1), and remove it from the array.
result array = { 3, 4, 0, 5 } 
proceed to STEP 4 "as planned"