n × n table board; every cell starts white. Each column may be painted black from the top down to any depth: from zero cells to the whole column (the painted part always starts at the top row and has no gaps).
After painting, a white cell scores if the cell directly **to its left or right** in the same row is black. The score is the sum of board[i][j] over all scoring cells.
Return the largest score you can get.board=[[0, 4, 0], [6, 0, 0], [0, 0, 5]] → 11
Paint the whole middle column. The white cells next to it, 6 and 5, score: 11. The 4 gets painted over, but saving it would cost the 6 or the 5.
board=[[3, 0, 2], [0, 7, 0], [1, 0, 4]] → 10
Paint one cell of the middle column and two cells of the right one. The 3 (next to the painted middle cell) and the 7 (next to the painted right column) score: 10.
board=[[1, 9], [9, 1]] → 10
Paint the right column completely and leave the left one white: 1 + 9 = 10.
n = board.length = board[i].length ≤ 100board[i][j] ≤ 10⁹board=[[0, 4, 0], [6, 0, 0], [0, 0, 5]]
11
Run checks the first 3 tests in your browser. Submit checks all 74 tests on the server, hidden ones included.