Solution of U

Let:

up[i][j] be the length of the longest sequence of 1's that starts at (i, j) and extends upwards.
left_up[i][j] be the length of the longest sequence of 1's that starts at (i, j), goes to the left 0 or more columns, and then extends upwards 1 or more rows.

When computing left_up[][], make sure that the sequence actually extends upwards, not just to the left. The following testcase fails numerous solutions (answer is 4, not 7):

The solution is constructed by joining an "L" shape, described by left_up[i][j-1] with a "|", described by up[i][j]. Complexity: O(N * M).

    1 #!/usr/bin/python3
    2 from copy import deepcopy
    3 
    4 n, m = map(int, input().split())
    5 a = [input() for i in range(n)]
    6 up = [[0 for j in range(m)] for i in range(n)]
    7 left_up = deepcopy(up)
    8 
    9 for j in range(m):
   10     up[0][j] = int(a[0][j])
   11 
   12 for i in range(1, n):
   13     for j in range(m):
   14         up[i][j] = up[i-1][j] + 1 if a[i][j] == '1' else 0
   15 
   16 for i in range(n):
   17     left_up[i][0] = up[i][0]
   18 
   19 for i in range(n):
   20     for j in range(1, m):
   21         if a[i][j] == '1':
   22             if up[i][j] > 1:
   23                 left_up[i][j] = up[i][j]
   24 
   25             if left_up[i][j-1] > 1:
   26                 left_up[i][j] = max(left_up[i][j], 1+left_up[i][j-1])
   27 
   28 sol = 0
   29 for i in range(n):
   30     for j in range(1, m):
   31         sol = max(sol, left_up[i][j-1] + up[i][j])
   32 
   33 if sol < 4:
   34     sol = 0
   35 
   36 print(sol)

Solution of U

Sponsors Gold