Here is one paper (Year 2004) which is close to the solution I proposed. Even though the author's claim the complexity is O(x*y) = O(n)...I am not sure about that after reading the paper. There is some "staircase" work involved at each cell, which will add to the complexity, which is ignored as negligible. I am not sure if I am being a bit biased towards the solution given in this forum ;-)
http://dl.acm.org/citation.cfm?id=996820Here is another one (Year 2010) which says the fastest existing algorithm is O(n * (log(n))^2)
http://arxiv.org/abs/1004.0558Wikipedia link.
http://en.wikipedia.org/wiki/Largest_em ... *******Can someone please point me to a faster solution than these?I am trying with some academic profs, yet to get any responses.The solution proposed here in this forum is of complexity (O(n*log(n)).