给定一个整数数组，发现使用该阵列的数字的数量最多，使得其是被3整除整数、数组、阵列、数量最多
例如：阵列：4,3,0,1,5 {假设所有的数字都是> 0。此外，在阵列的每个元素对应于一个数字。即阵列上的每个元素是0和9之间}
E.g.: Array: 4,3,0,1,5 {Assume all digits are >0. Also each element in array correspond to a digit. i.e. each element on the array is between 0 and 9. }
在上面的阵列，数量最多的是：5430 {用数字5，4,3和0从阵列}
In the above array, the largest number is: 5430 {using digits 5, 4, 3 and 0 from the array}
我的方法：
有关整除3，我们需要的数字的总和由3至整除。 因此，
For divisibility by 3, we need the sum of digits to be divisible by 3. So,
步骤1：从数组中删除所有的零 步骤2：这些零会在年底。 {由于他们没有影响的总和，我们必须找到最大的数} 步骤3：查找阵列的元件的子集（不包括零），使得数位的数量是最大，也即数字的总和是最大和的总和为被3整除。 STEP-4：所要求的数字组成的，在上述下降ordder发现设置的数字所以，主要的步骤是STEP-3即如何找到子集，它包含的元素尽可能多，使得它们的和S MAX是被3整除的。
So, the main step is STEP-3 i.e. How to find the subset such that it contains MAXIMUM possible number of elements such that their sum s MAX and is divisible by 3 .
我在想，也许步骤3可以通过首先把所有的元素，不断去除最小元素present在设定直到时间的总和是被3整除贪心选择来完成。
I was thinking that maybe Step-3 could be done by GREEDY CHOICE of first taking all the elements and keep on removing the smallest element present in the set till the time the sum is divisible by 3.
但我自己并不认为这种贪婪的选择会工作。
But i myself is not convinced that this GREEDY choice will work.
请告诉我们，如果我的做法是正确与否？ 如果是的话，请提出来怎么办步骤3？
Please tell if my approach is correct or not? If it is, then please suggest as to how to do Step-3 ?
另外，请提出任何其他可能的/高效的算法中。
Also, please suggest any other possible/efficient algo.
推荐答案
观察：如果你能得到一个数字，被3整除，你需要删除最多2个号码，以维持最佳解决方案。
Observation: If you can get a number that is divisible by 3, you need to remove at most 2 numbers, to maintain optimal solution.
一个简单的为O（n ^ 2）解决方案将检查所有的可能性，除去1个号码，如果没有有效，检查所有对（有为O（n ^ 2）的那些）。
A simple O(n^2) solution will be to check all possibilities to remove 1 number, and if none is valid, check all pairs (There are O(n^2) of those).
编辑：
O（N）解决方案：创建3桶 - bucket1 ， bucket2 ， bucket0 。每个将表示数字的模数3的值。忽略 bucket0 接下来的算法
O(n) solution: Create 3 buckets - bucket1, bucket2, bucket0. Each will denote the modulus 3 value of the numbers. Ignore bucket0 in the next algorithm.
让数组的总和为之。
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只需要2最小值和 bucket2 ，因为它是我们实际上从这些水桶使用的唯一的号码。
Note: You don't actually need the bucket, to achieve O(1) space - you need only the 2 minimal values from bucket1 and bucket2, since it is the only number we actually used from these buckets.
示例：
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"
