CareerCup

Divide the numbers into 3 groups:
A = { x | x % 3 == 0}, P = |A|   
B = { x | x % 3 == 1}, Q = |B|
C = { x | x % 3 == 2}, R = |C|

To pick 2 numbers whose sum is a multiple of 3 we can:
  (1) pick 2 from A which have C(P,2) cases
  (2) pick 1 from B, and 1 from C, which has Q*R cases

To pick 3 numbers whose sum is a multiple of 3 we can:
  (1) pick 3 from A, which has C(P,3) cases
  (2) pick 3 from B, which has C(Q,3) cases
  (3) pick 3 from C, which has C(R,3) cases
  (4) pick 1 from A, 1 from B, and 1 from C, which has P*Q*R cases

The question asks for "maximum" number of duplets/triplets and also specifies that number included once cannot be used again. Considering this, I would modify the solution provided by "Westlake" as below:

Divide the numbers into 3 groups:
A = { x | x % 3 == 0}, P = |A|   
B = { x | x % 3 == 1}, Q = |B|
C = { x | x % 3 == 2}, R = |C|

To maximize count, we should try to have as may duplets as possible:
Number of duplets from set A = int(P/2) ; combine pairs of elements of A
Number of duplets from Set B,C = min(Q, R) ; combine one element of B with one element of C

If Q>R, then there will be left over elements in Q and viceversa; These can be combined as triplets
Number of triplets = int(abs(Q-R)/3)
Any other left over elements of A, B, C cannot be combined to a multiple of 3 anymore.

Max count = int(P/2) + min(Q,R) + int(abs(Q-R)/3)

In addition to the DP solution , I think we can also use this:

consider this class:

class number implements Comparator {
 int value;
 int count;

 public int compareTo(number obj) {
	if (obj == count)
	return 0

	return obj < count ? -1 : 1;
 }
}

and have a HashMap like this

HashMap <int, number> values = SortedMap<int, number>()

and store the values in this hashMap as you iterate through the array, this will automatically sort the elements as you store them in the HashMap, upon completion, you can easily check
if the count of the elements is enough that they are multiples of 3 or not.

Using the HashMap will give us the O(1) access time.

P.S. You can obivously make the class 'number' more robust if you give your own implementations of the hashCode and equals method to avoid collisions in case of very large datasets.

Here is some C# code I put together. It's probably not the most efficient, but it works.

// the array
            int[] values = { 1, 6, 1, 7, 9, 25, 76, 3, 23, 86 };
            LinkedList<int> valuesList = new LinkedList<int>(values);

            // count of duples
            int count = 0;

            
            // find duples
            for (LinkedListNode<int> i = valuesList.First; i != null; i = i.Next)
            {
                for (LinkedListNode<int> j = i.Next; j != null; j = j.Next)
                {
                    if ((i.Value + j.Value) % 3 == 0)
                    {
                        // we found one so increment the count, and remove the
                        // values from the list
                        ++count;
                        valuesList.Remove(j);
                        //remove j first then save i.Next so we don't lose our place
                        LinkedListNode<int> k = i.Next;
                        valuesList.Remove(i);
                        i = k;
                    }
                }
            }

            // find triples
            for (LinkedListNode<int> i = valuesList.First; i != null; i = i.Next)
            {
                for (LinkedListNode<int> j = i.Next; j != null; j = j.Next)
                {
                    for (LinkedListNode<int> k = j.Next; k != null; k = k.Next)
                    {
                        if ((i.Value + j.Value + k.Value) % 3 == 0)
                        {
                            // we found one so increment the count, and remove the
                            // values from the list
                            ++count;
                            valuesList.Remove(j);
                            valuesList.Remove(k);
                            //remove j and k first then save i.Next so we don't lose our place
                            LinkedListNode<int> l = i.Next;
                            valuesList.Remove(i);
                            i = k;
                        }
                    }
                }
            }

Looks like the problem for DP.

why to go for DP unnecessary , i think we can do in generally linear time using boolean hash map as mentioned above:
below is not actual code,but i think it should work ...please comment guys..

bool map[3] = {false};
for(i=0;i<size;i++)
	map[i%3]++;
//in case of doublets
first_count = map[0]/3;
second_count  = min(map[1],map[2]);
return first_count+second_count;
//in case of triplets
first_count = map[0]/3 + map[1]/3 + map[2]/3;
second_count = min(map[0]-map[0]/3,map[1]-map[1]/3,map[2]-map[2]/3);
return first_count + second_count;