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&lt;tps.Length;i++)
    {
        Console.WriteLine(FindMaxLastK(tps, i, k));

    }
}
// method to check the maximum of last k items in the array
public int FindMaxLastK(int[] tps, int start, int k)
{
    k = k-1;
    int max = 0;
 while(k &gt;= 0 &amp;&amp; start &gt;= 0)
 {
     max = tps[start] &gt; 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 &gt; 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&lt;T&gt; MaxInSlidingWindow&lt;T&gt;(T[] values, int windowSize)
{
    var comparer = Comparer&lt;T&gt;.Default;
    var window = new LinkedList&lt;Tuple&lt;T, int&gt;&gt;();// Max at position and position

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

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

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

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