Jack love playing games, Gluttonous snake( an old game in Nokia era) is one of his favorite. However, after playing gluttonous snake so many times, he finally got bored with the game, so he changed the rules:

Rule 1: Write a code to find the Max sum path in a grid (2-D array), with dimension with n rows and m column (1<=n,m<=500)

Rule 2: In the 2D Array, each cell (elements) contains a value v in the array is from (-1<=v<=99999)

Rule 3. You can start from any position of the leftest column (border) of the array to the rightest(border) column of the array to calculate the Max Sum path.

Rule 4. You can move up, right, down, and CAN’T move left, and can visit each element only one time.

Rule 5.If the element is -1, it means the path is blocked, and you can’t go through the path (calculate it in the sum), you have to choose other path to calculate the sum.

For example, if a 4*4 array grid

{{-1,3,2,1}

{2,-1,2,4}

{2,2,-1,3}

{4,2,1,2}};

The max sum path is : (from grid[4][0])

4–>up–>2–>left–>2–>down–>2–>left–>

1–>left–>2–>up–>3–>up–>4–>up–>1

and the sum is 4+2+2+2+1+2+3+4+1 =21

[advanced_iframe securitykey=”undefined” src=”https://code.kodnest.com/” width=”100%” height=”600″]