// A team of programmers is considered to be solid if the qualification of each team member

// does not exceed the sum of qualifications of any other two team members.

// Assume that programmers qualifications (expressed as positive integers) are kept in an array

//     int [] q;

// Write a program that finds the maximum headcount of a possible solid team

// that can be formed with these programmers.

// Time: O(n * log n), where n = q.Length

using System;

​

public class Program

{

    public static int MaxSolidTeam(int [] q)

    {

        if(q.Length < 3)

            return q.Length;

        // q.Length >= 3

        Array.Sort(q);

        int first = 0;

        int next = 2;

        int countMax = 2;       // max solid headcount found so far

        // Invariant: countMax is max count among all solid teams in q[0..next-1] and

        //            team q[first..next-1] is solid and

        //            first + 1 < next <= q.Length

        while(next < q.Length)

        {

            if(q[next] <= q[first] + q[first+1])

            {

                next++;

                if(next - first > countMax)

                {

                    countMax = next - first;

                }

            }

            else

            {   // Team starting with q[first] cannot be increased more

                first++;

                if(first + 1 == next)

                    next++;

            }

        }

        return countMax;

    }

​

    public static void Test(int [] q)

    {

        Console.WriteLine("Max solid headcount of {{{0}}} is {1}", 

                          string.Join(" ", q), MaxSolidTeam(q));

    }

​

    public static void Main()

    {

        Test(new int[0]);

        Test(new[]{ 1, 100});

        Test(new[]{ 1, 1, 1, 1});

        Test(new[]{ 1, 1, 1, 10});

        Test(new[]{ 1, 1, 1, 5, 5, 5, 5});

        Test(new[]{ 11, 12, 13, 101, 102, 103, 104, 105});

    }

}

​