Algorithmically, you don't always have to examine all the elements. I'll explain how, but I'm not sure if it becomes sublinear time (growing slower than proportional to the number of array elements). In practical terms of elapsed run time, I'll focus on the dominant factor.
Starting with a straightforward program, you can use that to test that improved candidates still get the right result. In a non-learning situation, you could also decide if the initial program is fast enough for your purposes.
A straightforward program would scan each column once and each row once, count the longest sequence of 1's in each, and keep the highest count over all those.
Now to optimize, the question is what are we optimizing? Classic big-O algorithmic complexity would mainly count the number of probes into the array. Then given the longest run yet found of
l elements, if
n, you're done; no need to examine the remaining rows and columns. Else when starting on the next span, jump forward
l+1 elements. If that's a
0 or beyond the end of that row or column, then you don't need to probe any of the intermediate elements. Else if probing halfway to the previous probe finds
0, you don't need to probe the elements before that
0, etc. [So statistically, you can skip many array elements.]
But if you want to optimize elapsed time on modern hardware, the number of probes isn't what counts. I'll assume you're programming in a language that compiles (or JIT compiles) to native code so we're not dealing with interpreter overhead. (If you're writing this in Python, aim to do as much as possible in each call to Numpy.)
On modern hardware, the run time will be dominated by loading the data from RAM into the CPU cache. You can run many instructions in that amount of time. Those are the "probes" that matter, not testing the array elements. In that case what you want to optimize first is the data format so it's bit-packed into 8 elements per byte.
If the entire array is too large to fit into the CPU cache, then the next optimization step is to load it into the CPU only once or twice. For row-oriented data, scanning over the rows will be fine but scanning over the columns ought to reuse the data loaded per row, keeping partial results per column, or else make a second pass over columns but process a stripe that's 1 cache-line wide at a time (
8 x 64 bit-packed columns? whatever the cache-line size is on your CPU) so it can load each cache line only once.
This assumes you don't have to consider the time it takes to get the array into physical RAM (not virtual memory) and it all fits into RAM at once. If those assumptions don't hold, then what dominates is getting the data into RAM as fast as possible and only once, similar to the cache loading discussion. Either way, it's using the lesson of a B-tree.
Now you can consider parallelization across CPU cores. Do the cores share cache memory? Getting the cores usefully working in parallel can be subtle. Each core can work on a separate array row but reusing the loaded data for column stripes gets tricky.
It might also be interesting to use GPU vectorization.
l+1 skip probe can still help if applied at the level of cache-line loading or RAM loading, but it gets complicated esp. with the need to scan in 2 dimensions. Still, finding a run of length
l means you needn't examine any more data.