Hello, 大家好

请教大家一个问题

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

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

1. 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.

2. You can move up, right, down, and CAN'T move left, and can visit each element only one time.

3.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

int 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

我的想法是用递回function去跑 再把值传回来

谢谢大家