Find the numbers larger than them in the collection

Question

Let's say we have a collection of numbers like { 16,17,4,3,5,2 }. Now the objective is to find those numbers which are greater than the rest in the collection while compare with their right elements.

Indicates that 16 compared to 17 is less and cannot be consider. While 17 compared to 4,3 5 and 2 is always greater and hence will be consider. Likewise, 4 though greater than 3 abut less than 5 will be discarded. But 5 compared to 2 is greater. And since 2 is the rightmost element will always be consider. I have written the below program to do so and it works.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {

            var intCollection = new List<int>() { 16,17,4,3,5,2 };
            var discardedElements = new List<int>();

             for(int i=0;i< intCollection.Count;i++)
             {
                 for(int j=i+1;j< intCollection.Count; j++)
                 {
                     if (intCollection[i] < intCollection[j])
                     {
                         discardedElements.Add(intCollection[i]);
                     }
                 }
             }
             Console.WriteLine("Successful elements are");
             intCollection.Except(discardedElements).ToList().ForEach(i => Console.WriteLine("{0}", i));
             Console.ReadKey();
        } 
    }
}

Result

Successful elements are
17
5
2

But this program is not an optimized one. Any better algorithm for the same problem?

N.B.~ The program though apparently doesn't have any real time use but it will help in improving algorithm.

Answer 1

Here's a sample implementation:

public static IEnumerable<int> NumbersBiggerThanTheFollowingOnes(IList<int> numbers)
{
    if (numbers.Count <= 0)
        yield break;

    int max = numbers[numbers.Count - 1];
    yield return max; // Last element is considered bigger than the "following" ones.

    for (int i = numbers.Count - 2; i >= 0; --i)
    {
        if (numbers[i] <= max)
            continue;

        max = numbers[i];
        yield return max;
    }
}

Sample test code:

var intCollection = new List<int>() { 18, 10, 13, 16, 17, 4, 3, 5, 2 };
Console.WriteLine(string.Join(", ", NumbersBiggerThanTheFollowingOnes(intCollection).Select(x => x.ToString())));

Answer 2

You can go from right to left and filter increasing sequence of numbers

Example:

class Program
{
    static void Main( String[] args )
    {
        var intCollection = new List<Int32>() { 16, 17, 4, 3, 5, 2 };
        var intResults = new List<Int32>();
        var currentMaxValue = Int32.MinValue;

        for ( Int32 i = intCollection.Count - 1; i >= 0; --i )
        {
            if ( intCollection[ i ] > currentMaxValue )
            {
                currentMaxValue = intCollection[ i ];
                intResults.Insert( 0, intCollection[ i ] );
            }
        }

        Console.WriteLine( "Successful elements are" );
        intResults.ForEach( i => Console.WriteLine( "{0}", i ) );
        Console.ReadKey();
    }
}

Answer 3

You can iterate from the right to left, and keep the current maximum value then compare.

// Check empty intCollection
result.Add(intCollection[intCollection.Count-1]);
var currentMaxValue = intCollection[intCollection.Count-1];
for(int i = intCollection.Count - 2; i >= 0; --i) {
    if (intCollection[i] > currentMaxValue) {
        result.Add(intCollection[i]);
        currentMaxValue = intCollection[i];
    }
}