Maximize grid-path expression and count sawtooth subarrays

Problem 1: Maximize a valid expression along a grid path

You are given an m x n grid grid. Each cell contains either:

• an operator: '+' or '-', or
• a single digit character '0' … '9'.

You start at the top-left cell (0,0) and must reach the bottom-right cell (m-1,n-1) by moving only:

• right (r, c) -> (r, c+1), or
• down (r, c) -> (r+1, c).

As you traverse a path, you concatenate the visited cells (in order) to form an expression.

An expression is valid if it alternates strictly between numbers and operators:

• It must start with a digit.
• It must then alternate: digit, operator, digit, operator, digit, ...
• It must end with a digit.
• Therefore, it may not contain:
  • two consecutive operators (e.g., 0 ++ 1, 3 +- 4), or
  • two consecutive digits (e.g., 1 2 + 3, 5 - 6 3).

Evaluation rule: Evaluate the expression strictly left-to-right (since only + and - are present).

Task

Return the maximum possible evaluated value among all valid paths from (0,0) to (m-1,n-1).

Assumptions / constraints (for clarity)

• 1 <= m, n <= 50
• grid[r][c] is one of {'+','-','0'..'9'}
• If no valid path exists, return an agreed sentinel (e.g., null / None / -inf) as specified by the interviewer.

---

Problem 2: Count sawtooth (alternating parity) subarrays

A sawtooth sequence is a sequence of integers where adjacent elements have different parity (even/odd), i.e., it alternates between even and odd.

Given an integer array arr, count the number of contiguous subarrays that are sawtooth sequences.

• Subarrays of length 1 count as sawtooth by definition.

Examples

• arr = [1, 3, 5, 7, 9] → output 5 (only the 5 single-element subarrays).
• arr = [1, 2, 1, 2, 1] → output 15 (all subarrays alternate parity).
• arr = [1, 2, 3, 7, 6, 5] → output 12.

Constraints (for clarity)

• 1 <= len(arr) <= 2 * 10^5
• |arr[i]| <= 10^9

Task

Return the total number of contiguous sawtooth subarrays.