How to determine maximum sum in a path through 2-D array when all positions cannot be visited?

Question

The problem that I am stuck is that a person needs to go from the top-left of a 2-D array containing integers to the bottom-right position, gaining maximum possible score, either moving down or right. However, if a position A[i][j] is less than 0, then the person can't move past it and a amount equal to this negative value will be subtracted from the score every time the person visits a neighborhood of such position. I know that its a standard DP problem and that I could make a array T[][] with T[i][j] representing the maximum score till position i,j from 0,0. However, I am unable to come up with any proper implementation of the condition that person should not move past the cell marked with a negative integer. For example, if rows=2;column=3; and

A= | 0  -4   8 |
   | 1   1   0 |

then i want the answer to be -6, i.e. the matrix T should be

 T=| 0  -4   X |
   | -3 -6  -6 |

1. Given that at the starting and ending positions the person is not 'robbed' off his score.
2. X denotes that the corresponding position can't be reached by the man. In the above case the man cannot cross A[0][1] to go to A[0][2]
3. T[row-1][column-1] is the answer of the question i.e. the maximum score the person can obtain starting from A[0][0] to A[row-1][column-1]

Answer 1

I was following the same train of thought as suggested in the answer by dwrd, so I tried implementing it in Python. There are a few things to consider that I hadn't thought initially but I think I finally got it working.

Here's the code, it surely needs some polishing up, but it's a start:

def get_score(M, i, j):
    "Get the final score for position [i, j.]"
    score = 0

    if M[i][j] < 0:
        score = -float('inf')
    else:
        score = M[i][j]
        score = score + penalty(M, i - 1, j - 1)
        score = score + penalty(M, i - 1, j + 1)
        score = score + penalty(M, i + 1, j - 1)
        score = score + penalty(M, i + 1, j + 1)
        score = score + penalty(M, i - 1, j)
        score = score + penalty(M, i, j - 1)
        score = score + penalty(M, i + 1, j)
        score = score + penalty(M, i, j + 1)

    return  score

def penalty(M, i, j):
    "Calculate the penalty for position [i, j] if any."
    if i >= 0 and i < len(M) and j >= 0 and j < len(M[0]):
        return (0 if M[i][j] > 0 else M[i][j])

    return 0

def calc_scores(M):
    "Calculate the scores matrix T."
    w = len(M[0])
    h = len(M)
    T = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        for j in range(w):
            T[i][j] = get_score(M, i, j)

    T[0][0] = 0
    T[h - 1][w - 1] = 0

    return T

def calc_max_score(A, T):
    "Calculate max score."
    w = len(A[0])
    h = len(A)
    S = [[0 for _ in range(w + 1)] for _ in range(h + 1)]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            S[i][j] = max(S[i - 1][j], S[i][j - 1]) + T[i - 1][j - 1]

            # These are for the cases where the road-block
            # is in the frontier
            if A[i - 1][j - 2] < 0 and i == 1:
                S[i][j] = -float('inf')

            if A[i - 2][j - 1] < 0 and j == 1:
                S[i][j] = -float('inf')
    return S

def print_matrix(M):
    for r in M:
        print r

A = [[0, -4, 8], [1, 1, 0]]
T = calc_scores(A)
S = calc_max_score(A, T)

print '----------'
print_matrix(T)
print '----------'
print_matrix(S)
print '----------'

A = [[0, 1, 1], [4, -4, 8], [1, 1, 0]]
T = calc_scores(A)
S = calc_max_score(A, T)

print '----------'
print_matrix(T)
print '----------'
print_matrix(S)
print '----------'

You get the following output:

----------
[0, -inf, 4]
[-3, -3, 0]
----------
[0, 0, 0, 0]
[0, 0, -inf, -inf]
[0, -3, -6, -6]
----------

----------
[0, -3, -3]
[0, -inf, 4]
[-3, -3, 0]
----------
[0, 0, 0, 0]
[0, 0, -3, -3]
[0, 0, -inf, 1]
[0, -3, -6, 1]
----------

Answer 2

The idea is emulating inability to move into negative cell with negative infinity result that will be never selected as maximum. Pseudocode:

int negativePart(int i, int j)
{
    if (i < 0 || j < 0)
        return 0;
    return A[i, j] < 0 ? A[i, j] : 0;
}

int neighborInfluence(int i, int j)
{
    if (int == Height -1 && j == Width - 1)
        return 0;
    return negativePart(i-1, j-1) + negativePart(i-1,j)+// so on, do not think about negative indexes because it was already processed in negativePart method
}

int scoreOf(int i, int j)
{
    return A[i,j] < 0 ? <NegativeInfinity> : A[i,j] + neighborInfluence(i,j);
}

//.......

T[0,0] = A[0,0];
for (int i = 1; i < heigth; ++i)
{
    T[i, j] = T[i - 1, 0] + scoreOf(i, 0);
}

for (int i = 1; i < width; ++i)
{
    T[0, i] = T[0, i - 1] + scoreOf(0, i);
}

for (int i = 1; i < heigth; ++i)
{
    for (int j = 1; j < width; ++j)
    {
        T[i, j] = max(T[i - 1, j], T[i, j - 1]) + scoreOf(i, j);
    }
}