Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### eleganc's blog

By eleganc, history, 10 months ago,

Given a matrix consisting of characters of the type:

1. Single digits
2. '-'
3. '+'

Find the maximum value which can be evaluated using a valid expression in the matrix.

A valid expression is defined as a contiguous array:

1. Starts from any cell with a numeric value and is either in the left to right direction or in top to bottom direction.
2. The final expression doesn't contain any consecutive operators. Eg. '3' '+' '-' '1' is not allowed.

Example TC:

n = 7, m = 5

matrix =

'1' '+' '3' '-' '2'

'-' '2' '+' '3' '+'

'1' '-' '4' '-' '4'

'+' '2' '-' '7' '+'

'2' '+' '5' '+' '9'

'+' '1' '+' '8' '-'

'2' '-' '0' '-' '2'

Answer: 2 + 5 + 9 = 16 evaluates to the maximum value. Hence the answer is 16.

Caution: We may have a matrix like ['4' '4' '5' '-' '-' '5' '1'], in this case we are free to take 445 or 4, 5, 5, or 44 to 45

• 0