### aeonary's blog

By aeonary, history, 4 months ago,

Given a grid of size $M \times N, (1 \le M, N \le 2000)$ where each cell contains an integer $A_ij, (|A_ij| \le 250)$. We have to find the maximum path from (1, 1) to any cell in the last row. Allowed moves are right, left, and bottom.

I've used DP to solve this problem, where $DP[i][j]$ equals the maximum path sum from (1, 1) to (i, j). Then I got 2 cases: the first one is that we can get to (i, j) from (i — 1, j), and from (i, j) we can move left or right such that the left sum and the right sum is positive, so initially, $DP[i][j] = DP[i-1][j] + A[i][j] + maxPrefix[i][j - 1] + maxSuffix[i][j + 1]$. Cases number 2 is that we can get to (i, j) from (i, k), and (i, k) is from (i — 1, k), and then from (i, k) we can move to the left if $k < j$, then move to the right of j: $DP[i][j] = DP[i - 1][k] + sum[j..k] + maxPrefix[i][k - 1] + maxSuffix[i][j + 1]$ or we can move to the right from (i, k) if $j < k$, then move to the left of j: $DP[i][j] = DP[i - 1][k] + sum[j..k] + maxPrefix[i][j - 1] + maxSuffix[i][k + 1]$. But I got WA with this solution, please help me to solve this problem (sorry that I don't have the submission link).

• -8

 » 4 months ago, # |   0 This is my code