First, let's take a look at the limits: N ≤ 1000. This suggests the complexity O(N^2). The problem can be solved by DP and the solution should be pretty straight forward.
To make a good solution we'll solve a simpler problem at first. Let's assume D means just one step down. This particular problem can be solved by the folowing DP:
dp[dir][i][j] = the largest sum of a sequence that ends in position (i, j), considering that the snake is coming from direction dir (0 for left or 1 for right).
Returning to the initial problem, the DP seems simpler now: dp[dir][des][i][j] = the largest sum of a sequence that ends in position (i, j), considering that the snake is coming from direction dir (0 for left, 1 for right) and is descending or not (des = 0/1).
The following cases must be analyzed:
- The snake goes down.
- The snake continues to move to the left or to the right.
- The snake stops descending and swaps the direction.
Time complexity: O(N^2).
