给定一个整数数组，使用数组中的数字找到最大的数字，使其能被 3 整除

例如：数组：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. STEP-4：所需的数字由上述找到的集合中按降序排列的数字组成。

所以，主要步骤是STEP-3，即如何找到子集，使其包含最大可能数量的元素，使其总和为 MAX 并且可被 3 整除 .

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

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

请告诉我的方法是否正确。 如果是，那么请建议如何执行步骤 3？

另外，请建议任何其他可能/有效的算法。

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

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

EDIT:
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)空间 - 您只需要 2 个最小值bucket1 and bucket2，因为它是我们实际使用的这些桶中的唯一数字。

Example:

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"