PoisonousPlants.cs

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

using NUnit.Framework;
using NUnitLite.Runner;

namespace PoisonousPlants
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new TextUI().Execute(new[] { "-noheader" });
        }

        private static int Solve(IEnumerable<int> pesticides)
        {
            var plants = new Stack<Plant>();
            var maxDaysAlive = 0;

            foreach (var pesticide in pesticides)
            {
                var daysAlive = 0;
                while (plants.Count > 0 && pesticide <= plants.Peek().Pesticide)
                {
                    daysAlive = Math.Max(daysAlive, plants.Pop().DaysAlive);
                }

                daysAlive = plants.Count == 0 ? 0 : daysAlive + 1;
                maxDaysAlive = Math.Max(maxDaysAlive, daysAlive);
                plants.Push(new Plant(pesticide, daysAlive));
            }

            return maxDaysAlive;
        }

        private struct Plant
        {
            public Plant(int pesticide, int daysAlive)
            {
                Pesticide = pesticide;
                DaysAlive = daysAlive;
            }

            public int Pesticide { get; }

            public int DaysAlive { get; }
        }

        [Test]
        public void SolutionWorksForSampleInput()
        {
            var input = new[] {6, 5, 8, 4, 7, 10, 9};
            Assert.AreEqual(2, Solve(input));
        }

        [Test]
        public void SolutionSolvesPathologicalCaseQuickly()
        {
            const int inputSize = 100000;
            var input = new[] {1}.Concat(Enumerable.Repeat(2, inputSize - 1));
            Assert.AreEqual(inputSize - 1, Solve(input));
        }
    }
}