C# implementation of algorithm of calculation LargestRectangle

algorithms-stack-largest-rectangle.cs

/// Description of the problem can be found at https://www.hackerrank.com/challenges/largest-rectangle/editorial
/// As a real use case we could consider usage of this algorithm to find out the largest rectangular subarray containing only ones.
/// For more details go to http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529
public int LargestRectangle(string input)
{
  var heights = input.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
    .Select(int.Parse)
    .Concat(new[] { 0 }) // add tail 0 to force calculation when we reach the last element
    .ToArray();
  var positions = new Stack<int>();
  var largest = 0;
  for (int i = 0; i < heights.Length; i++)
  {
    while (positions.Count > 0 && heights[positions.Peek()] > heights[i])
    {
      int height = heights[positions.Pop()];
      int width = positions.Count == 0 ? i : i - positions.Peek() - 1;
      largest = Math.Max(largest, height * width);
    }
    positions.Push(i);
  }
  return largest;
}