Tweets per second calculator (Talent Buddy)

This challenge is from Talent Buddy:



Tweets per second



Japan Castle in the Sky airing broke a Twitter record on August 3,
2013. At one point during the classic anime movie showing, people submitted 143,199 tweets per second. This particular spike was about
25 times greater than Twitter’s steady state.


Given an array of integers representing the number of tweets recorded
every second and an integer value K, your task is to write a function
that prints to the standard output (stdout) the highest number of
tweets recorded between each second in the array and the past K
seconds before it


Note that your function will receive the following arguments: tps,
which is an array of integers representing the number of tweets
recorded every second, and k, which is the integer number mentioned
above.


Data constraints: the length of the array above will not exceed
500,000 numbers


Efficiency constraints: your function is expected to print the
requested result and return in less than 2 seconds


Example Input


tps: 6, 9, 4, 7, 4, 1


k: 3 Output


6 9 9 9 7 7 Please Note: The above program should run in below 2
seconds

Below is my code in c#

public void tweets_per_second(int[] tps, int k) {
    // Write your code here
    // To print results to the standard output you can use Console.WriteLine()
    // Example: Console.WriteLine("Hello world!");

    for(int i=0; i= 0 && start >= 0)
 {
     max = tps[start] > max? tps[start]:max;
     k--;
     start--;
 }
    return max;
}

The code has been accepted by the website, but somehow I feel it can be done better. Any suggestions?

Naming

Your FindMaxLastK method doesn't describe it's intention very well, what is tps and k when viewed at a glance?. What you have is a windowing function finding the max within that window. Name your function after that:

static int MaxInWindow(int[] values, int start, int trailingWindowSize)

The conditional expression in your max function could be clearer if you used Math.Max(int, int)

My implementation would look like:

public static int MaxInWindow(int[] values, int start, int trailingWindowSize)
{
    //TODO Validate arguments
    var lowerBound = Math.Max(start - trailingWindowSize, -1);
    var max = values[start];
    for (int index = start - 1; index > lowerBound; index--)
    {
        max = Math.Max(max, values[index]);
    }
    return max;
}

Performance

Your solution is O(m * n) where m is the number of seconds and n is the window size. I just saw the answer in a related question and the optimal solution is O(m).

The solution uses a LinkedList to keep track of the max in the window. Here is my implementation in C#:

public static IEnumerable MaxInSlidingWindow(T[] values, int windowSize)
{
    var comparer = Comparer.Default;
    var window = new LinkedList>();// Max at position and position

    var length = values.Length;
    for (var index = 0; index < length; index++)
    {
        var value = values[index];
        while (window.Count != 0 && comparer.Compare(window.Last.Value.Item1, value) < 0)
        {
            window.RemoveLast();
        }

        window.AddLast(Tuple.Create(value, index));

        while (window.First.Value.Item2 <= index - windowSize)
        {
            window.RemoveFirst();
        }

        yield return window.First.Value.Item1;
    }
}

StackExchange Code Review Q#92343, answer score: 2