#  On Linear Solution of Cherry Pickup II.
Max Weight of Two Disjoint Paths
in Node-Weighted Gridlike DAG

Igor N. Tunev

<EMAIL_ADDRESS>
###### Abstract

“Minimum Falling Path Sum” (MFPS) is classic question in programming – “Given
a grid of size $N{\times}N$ with integers in cells, return the minimum sum of
a falling path through grid. A falling path starts at any cell in the first
row and ends in last row, with the rule of motion – the next element after the
cell $(i,j)$ is one of the cells $(i+1,j-1)$, $(i+1,j)$ and $(i+1,j+1)$”. This
problem has linear solution (LS) (i.e. ${\textit{O}}(N^{2})$) using dynamic
programming method (DPM).

There is an Multi-Agent version of MFPS called “Cherry Pickup II” (CP2) [1].
CP2 is a search for the maximum sum of 2 falling paths started from top
corners, where each covered cell summed up one time. All known fast solutions
of CP2 uses DPM, but have ${\textit{O}}(N^{3})$ time complexity on grid
${N\times}N$. Here we offer a LS of CP2 (also using DPM) as finding maximum
total weight of 2 vertex-disjoint paths. Also, we extend this LS for some
extended version of CP2 with wider motion rules.

Key words: dynamic programming, directed acyclic graph, grid, time complexity,
combinatorial optimization, linear algorithm, disjoint paths, set

##  1 Introduction

CP2 is Multi-Agent extension of well known problem, sometimes called as
“Minimum Falling Path Sum” in [2], and its variations like “Gold Mine” in [3]
and “Minimum Path Sum” in [4].

There is variation of CP2 called “Cherry Pickup” in [5] sometimes called as
“Diamond Mine” (DM) in [6]. DM extended with ability to lock cells, but still
has linear reducing to CP2, even as finding maximum sum of 2 node-disjoint
paths, as will be described below.

For solution of CP2 we offer algorithm for search of 2 paths without crossing
with maximum common sum. Thus, this LS can be represented as LS for a simple
case of Multi-Agent Path Finding problem (MAPF) with maximizing/minimizing
deliveries/cost. The MAPF is the problem of finding collision-free paths for a
team of robots from their locations to given destinations in a known
environment.

Disjoint paths (DP) problem is one of the well known problems in algorithmic
graph theory and combinatorial optimization. There are many LSs of finding
fixed number of DP on spetial cases of graphs. For example, Scheffler found LS
on graphs with bounded tree-width [7]. In the paper of Golovach, Kolliopoulos,
Stamoulis and Thilikos [8] offered LS on a planar graphs. Most closely for our
purpose is LS proposed by Tholey for 2 DP on directed acyclic graphs (DAGs)
[9]. But we need in LS on node- or edge-weighted DAGs.

Suitable for our purpose the Suurballe’s algorithm (SA) on edge-weighted
digraphs [10], but with not linear complexity, as we will show further. We
offer LS for finding 2 node-DP with maximum total weight on some special case
of node-weighted DAGs.

###  1.1 Problem description

Given a grid ${\sf g}$ of size ${\textit{H}}{\times}{\textit{W}}$ with
addressable cells from $(0,0)$ to $({\textit{H}}{-}1,{\textit{W}}{-}1)$. Each
cell in grid represents the number of cherries that we can collect. There are
2 robots in corners $(0,0)$ and $(0,{\textit{W}}{-}1)$, that can collect
cherries. When a robot is located in a cell, It picks up all cherries of this
cell, and this cell becomes an empty. We need to collect maximum number of
cherries, using these robots. Robots can move according to following rules:

  * (r1)

From cell $(i,j)$, robots can move to cell $(i+1,j-1)$, $(i+1,j)$ or
$(i+1,j+1)$;

  * (r2)

When both robots stay on the same cell, only one of them takes the cherries;

  * (r3)

Both robots cannot move outside of the grid at any moment;

  * (r4)

Both robots should reach the bottom row in the grid.

The fastest solutions, found by us on the network, have
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}}{\cdot}\min\\{{\textit{H}},{\textit{W}}\\})$
complexity. Same complexity can be reached using next naive DPM with 3D
structure $dp$: for each $i=0,...,{\textit{H}}{-}2$ and $0\leq
j_{1}<j_{2}\leq{\textit{W}}-1$

$dp[i][j_{1}][j_{2}]=\max_{j_{1}-1\leq k_{1}\leq j_{1}+1,j_{2}-1\leq k_{2}\leq
j_{2}+1,0\leq k_{1}<k_{2}<{\textit{W}}}\\{dp[i+1][k_{1}][k_{2}]+{\sf
g}_{i,j_{1}}+{\sf g}_{i,j_{2}}\\}$

where $dp[{\textit{H}}-1][j_{1}][j_{2}]={\sf g}_{{\textit{H}}-1,j_{1}}+{\sf
g}_{{\textit{H}}-1,j_{2}}$.

Thus, if $2{\textit{H}}>{\textit{W}}$, then we can to find this $dp$ table and
return $dp[0][0][{\textit{W}}{-}1]$. If $2{\textit{H}}\leq{\textit{W}}$, then
any paths that started from $(0,0)$ and $(0,{\textit{W}}-1)$ don’t intersect
with each other, then this case can be reduced to the original problem with
one path.

Here we answer the question – is there a solution of CP2 with
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}})$ complexity? Also, we show LS
for some extension of CP2 (without strong proof of correctness).

###  1.2 Near linear solution using Suurballe’s algorithm

Here we show the simple reduction of CP2 to the well known method for finding
2 node-DP in a edge-weighted digraph (without proof of correctness).

SA is an algorithm for finding 2 node-DP in a nonnegatively-weighted (edge-
weighted) digraph, such that both paths connect the same pair of nodes and
have minimum total weight.

Let $m$ is maximum value of ${\sf g}$. Denote by ${\sf g}^{\prime}$ the edge-
weighted DAG with ${\textit{W}}{\cdot}{\textit{H}}{+}2$ nodes and
$3({\textit{W}}{-}2)({\textit{H}}{-}1)+4({\textit{H}}{-}1){+}{\textit{W}}{+}2$
links (directed edges) such that:

1) Each cell of ${\sf g}$ contains one node of ${\sf g}^{\prime}$. And 2 more
nodes $s$ and $t$.

2) Weight of link from node in cell $(i,j)$ to node in cell $(i+1,j^{\prime})$
is $m-{\sf g}_{i,j}$, for each $0\leq i<{\textit{H}}-1$, $0\leq
j<{\textit{W}}$ and $\max\\{0,j-1\\}\leq
j^{\prime}\leq\min\\{j+1,{\textit{W}}-1\\}$. Weights of 2 links from node $s$
to nodes in cells $(0,0)$ and $(0,{\textit{W}}-1)$ are $0$. And weight of link
from node in cell $(H-1,j)$ to $t$ is $m-{\sf g}_{H-1,j}$ for each $0\leq
j<{\textit{W}}$.

Now we can find 2 node-DP from $s$ to $t$ in ${\sf g}^{\prime}$ using SA. The
total weight of found 2 paths is minimum sum $M^{\prime}$. Then required
answer is $m{\cdot}{\textit{H}}-M^{\prime}$.

####  1.2.1 Complexity analysis

Let denote the set of edges and nodes of graph ${\sf g}^{\prime}$ as $E({\sf
g}^{\prime})$ and $V({\sf g}^{\prime})$ respectively. The case when
${\textit{W}}>2\cdot{\textit{H}}$ is trivial (because of this case can be
reduced to problem with one robot in linear time), therefore we can assume
that ${\textit{W}}\leq 2\cdot{\textit{H}}$.

Complexity of SA equal to complexity of Dijkstra’s algorithm (DA) [11]. As
published in [12] by Fredman and Tarjan the DA can be improved using Fibonacci
heap and performed in ${\textit{O}}(|E({\sf g}^{\prime})|+|V({\sf
g}^{\prime})|\log(|V({\sf g}^{\prime})|))$. Then we get complexity
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}}{\cdot}\log({\textit{H}}{\cdot}{\textit{W}}))={\textit{O}}({\textit{H}}{\cdot}{\textit{W}}{\cdot}\log({\textit{H}}))$.

There are other optimisations of DA for our purposes. One of them is algorithm
of shortest path (SP) on DAGs. Using topological sorting we can find SP on DAG
in linear time as in [14]. But SA uses search of SP twice. And before second
search of SP, the graph is not a DAG in common case.

Other optimisation for bounded integers weights by some value $C$. But all
such optimisations is not linear. Most fast of them, in our case, published in
[13] by Ahuja, Mehlhorn, Orlin and Tarjan (AMOT). This algorithm works in
${\textit{O}}(|E({\sf g}^{\prime})|\cdot\log\log(C))$ time. Thus, if $C$ has
polynomial dependence on $H$, then SA with AMOT optimisation has complexity
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}}{\cdot}\log\log(H))$.

Here we offer linear solution when almost all absolute values of the grid
${\sf g}$ are close to $C$.

##  2 Defaults

We can assume that absolute values in cells of grids are bounded by value
$C=f({\textit{H}})$, for some positive real function $f$ (i.e. in common case
some values of ${\sf g}$ can be negative). Exception for values equals to
$-\infty$ – this value is used for bounding of paths.

Also we assume that $\Theta({\textit{H}}{\cdot}{\textit{W}})$ of cells have
values $\Theta(f({\textit{H}}))$. I.e. the length of input data is
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}}{\cdot}\log(f({\textit{H}})))$.
And assume that ${\textit{H}},{\textit{W}}\geq 2$.

######  Definition 1.

The ${\sf F}_{i,j}(g^{\prime})$ is table, defined by grid $g^{\prime}$ of size
${\textit{H}}\times{\textit{W}}$, such that

${\sf F}_{i,j}(g^{\prime})=\begin{cases}0&i={\textit{H}},\\\
g^{\prime}_{i,j}+\max\\{{\sf F}_{i+1,\max\\{j-1,0\\}}(g^{\prime}),{\sf
F}_{i+1,j}(g^{\prime}),{\sf
F}_{i+1,\min\\{j+1,{\textit{W}}-1\\}}(g^{\prime})\\}&i=0,...,{\textit{H}}-1\end{cases}$

for each $0\leq j\leq{\textit{W}}-1$. By default ${\sf F}_{i,j}$ means ${\sf
F}_{i,j}({\sf g})$

######  Definition 2.

By path we call an ordered finite sequence (vector) of cells in grid (by
default in ${\sf g}$) using rules (r1) and (r3). I.e. after not the last cell
$(i,j)$ the next cell either $(i+1,\max\\{j-1,0\\})$ or $(i+1,j)$ or
$(i+1,\min\\{j+1,{\textit{W}}-1\\})$.

Location of path in grid can be obtained by addressing to row number. For
example, at $i$-th row the path $t$ located at $t(i)$-th column.

######  Definition 3.

Let $t$ is path from row $i_{1}$ to row $i_{2}$ ($i_{1}\leq i_{2}$), then
denote sum of $t$ as ${\sf PS}(t)$. I.e.

${\sf PS}(t)=\sum_{k=i_{1}}^{i_{2}}{g_{k,t(k)}}.$

Table ${\sf F}$ is known dynamic programming method of search for maximum (or
minimum, if we change the $\max$ to $\min$ in the definition of ${\sf F}$) sum
of falling path. Also, using ${\sf F}$ we can choose one of these paths with
maximum sum.

######  Definition 4.

Call path $t$ as path defined by ${\sf F}_{i^{\prime},j^{\prime}}$ if
$t(i^{\prime})=j^{\prime}$ and for each
$i{=}i^{\prime}+1,...,{\textit{H}}{-}1$

$t(i)\in\operatorname*{arg\,max}_{j=\max\\{t(i{-}1)-1,0\\},...,\min\\{t(i{-}1)+1,{\textit{W}}{-}1\\}}\\{{\sf
F}_{i,j}\\}.\\\ $

Since the ${\sf F}$ is well known DPM for solution of MFPS, then next simple
notes we will not prove

######  Note 1.

$t$ defined by ${\sf F}_{i,j}({\sf g})$ iif ${\sf PS}(t)={\sf F}_{i,j}({\sf
g})$.

######  Note 2.

If $t$ starts from cell $(i,j)$ then ${\sf PS}(t)\leq{\sf F}_{i,j}({\sf g})$.

######  Definition 5.

${\sf l_{p}}$ is leftmost path defined by ${\sf F}_{0,0}$. I.e. ${\sf
l_{p}}(0){=}0$ and for each $i{=}1,...,{\textit{H}}{-}1$

${\sf l_{p}}(i)=\min\operatorname*{arg\,max}_{j=\max\\{{\sf
l_{p}}(i{-}1)-1,0\\},...,\min\\{{\sf
l_{p}}(i{-}1)+1,{\textit{W}}{-}1\\}}\\{{\sf F}_{i,j}\\}.\\\ $

And ${\sf r_{p}}$ is rightmost path defined by ${\sf F}_{0,W{-}1}$. I.e. ${\sf
r_{p}}(0)={\textit{W}}{-}1$ and for each $i=1,...,{\textit{H}}{-}1$

${\sf r_{p}}(i)=\max\operatorname*{arg\,max}_{j=\max\\{{\sf
r_{p}}(i{-}1)-1,0\\},...,\min\\{{\sf
r_{p}}(i{-}1)+1,{\textit{W}}{-}1\\}}\\{{\sf F}_{i,j}\\}.\\\ $

By Note 1 we get ${\sf PS}({\sf l_{p}})={\sf F}_{0,0}({\sf g})$ and ${\sf
PS}({\sf r_{p}})={\sf F}_{0,{\textit{W}}-1}({\sf g})$. Then, if ${\sf l_{p}}$
don’t intersect with ${\sf r_{p}}$, then required answer is ${\sf
F}_{0,0}+{\sf F}_{0,{\textit{W}}-1}$. This case can be checked in
$O({\textit{H}}\times{\textit{W}})$ of linear operations with numbers of
length $\log({\textit{H}})$. Further we suppose that ${\sf l_{p}}$ intersects
with ${\sf r_{p}}$.

Due to simmetry of rules by left and right for input data and moving, all
properties we will formulate for one side only. For other side all these
properties can be formulated and proved similarly.

By default, if name of pair of paths starts from letters $"l"$ and $"r"$, then
it means that path with first letter $"l"$ located on the left side of path
with first letter $"r"$.

When we talk ”for each $i$” for rows, we mean ”for each
$i=0,...,{\textit{H}}-1$”. When we talk ”for each $j$” for columns, we mean
”for each $j=0,...,{\textit{W}}-1$”.

##  3 Definitions and properties

######  Definition 6.

Let $0\leq i_{1}<i_{2}\leq{\textit{H}}-1$ and path $t$ with begining not after
$i_{1}$-th row and with ending not before $i_{2}$-th row. By subpath between
rows $i_{1}$ and $i_{2}$ of $t$ we call path
$((i_{1},t(i_{1})),(i_{1}+1,t(i_{1}+1)),...,(i_{2},t(i_{2})))$ and denote it
as $t[i_{1},...,i_{2}]$.

By default $i_{1}=0,i_{2}={\textit{H}}-1$.

######  Definition 7.

Let $t$ is path from row $i_{1}$ to row $i_{2}$. By tail of path $t$ from
$(i,t(i))$ (or from $i$-th row) we call subpath $t[i,...,i_{2}]$ and denote as
$t[i,...]$.

By prefix (or head) of path $t$ with end on $(i,t(i))$ we call subpath
$t[i_{1},...,i]$ and denote $t[...,i]$.

######  Definition 8.

Let $t_{1}$ and $t_{2}$ are paths. Suppose that $t_{1}$ ends after $(i-1)$-th
row and $t_{2}$ starts before $(i+2)$. By concatenation $t$ of $t_{1}[...,i]$
and $t_{2}[i+1,...]$ we call the sequence of cells ordered by rows where
$t[...,i]=t_{1}[...,i]$ and $t[i+1,...]=t_{2}[i+1,...]$.

######  Note 3.

Let $t_{1}$ and $t_{2}$ are paths and $t_{1}(i)=t_{2}(i)$ then concatenation
$t$ of $t_{1}[...,i]$ and $t_{2}[i+1,...]$ is path. I.e. $t$ satisfy the rules
(r1) and (r3).

######  Definition 9.

The path $t$ intersect cell $(k,m)$ when $t(k)=m$.
The path $t_{1}$ intersects path $t_{2}$ at $i$-th row when either
$(t_{1}(i-1)\leq t_{2}(i-1)$ and $t_{1}(i)\geq t_{2}(i))$ or $(t_{1}(i-1)\geq
t_{2}(i-1)$ and $t_{1}(i)\leq t_{2}(i))$.

Note that ”paths without intersection” (PWOI) is more stronger than ”node-
disjoint paths” (or ”cell-disjoint paths” in our case).

######  Property 1.

Let path $p_{1}$ intersects the path $p_{2}$ at row $i{+}1$ where
$p_{1}(i)\leq p_{2}(i)$ and $p_{1}(i{+}1)\geq p_{2}(i{+}1)$, then tails of
$p_{1}$ and $p_{2}$ from row $i+1$ are swapable. It mean that concatenation of
$p_{1}[0,...,i]$ and $p_{2}[i+1,...]$ is path, and concatenation of
$p_{2}[...,i]$ and $p_{1}[i+1,...]$ is path too.

###### Proof.

There are 2 case of intersections:

  * •

When $p_{1}(i)=p_{2}(i)$.

Then using rule (r1) we get $p_{1}(i)-1=p_{2}(i)-1\leq p_{2}(i+1)\leq
p_{2}(i)+1=p_{1}(i)+1$.

I.e. $p_{1}(i)-1\leq p_{2}(i+1)\leq p_{1}(i)+1$. Thus $p_{1}[...,i]$ can be
contiued by $p_{2}[i+1,...]$ without breaking of rule (r1). A similar proof
for concatenation of $p_{2}[...,i]$ and $p_{1}[i+1,...]$.

  * •

When $p_{1}(i)<p_{2}(i)$.

Then using rule (r1) we get $p_{1}(i)-1<p_{2}(i)-1\leq p_{2}(i+1)\leq
p_{1}(i+1)\leq p_{1}(i)+1$. And again, $p_{1}[...,i]$ can be contiued by
$p_{2}[i+1,...]$ without breaking of rule (r1).

Also using (r1) we get $p_{2}(i)-1\leq p_{2}(i+1)\leq p_{1}(i+1)\leq
p_{1}(i)+1<p_{2}(i)+1$. Thus $p_{2}[...,i]$ can be continued by
$p_{1}[i+1,...]$ without breaking of rule (r1).

Since $p_{1}$ and $p_{2}$ satisfy the rule (r3), then any subpaths of them are
satisfy the rule (r3).

Thus all these concatenations satisfy the rules (r1) and (r3). I.e.
concatenation of $p_{1}[0,...,i]$ and $p_{2}[i+1,...]$ is path, and
concatenation of $p_{2}[...,i]$ and $p_{1}[i+1,...]$ is path too. ∎

######  Note 4.

If path $t$ defined by ${\sf F}_{i,j}$, then for any row $i^{\prime}\geq i$ we
get ${\sf PS}(t[i^{\prime},...])={\sf F}_{i^{\prime},t(i^{\prime})}$.

######  Property 2.

Consider path $t_{1}$ started from cell $(i_{1},j_{1})$ and has maximum sum
(i.e. $t_{1}$ is path defined by ${\sf F}_{i_{1},j_{1}}$). Suppose that
$t_{1}$ intersect $(k_{1},m_{1})$-th and $(k_{2},m_{2})$-th cells, where
$k_{2}>k_{1}\geq i_{1}$. Then:

  1. 1.

${\sf PS}(t_{1}[k_{1},...,k_{2}-1])={\sf F}_{k_{1},m_{1}}-{\sf
F}_{k_{2},m_{2}}$;

  2. 2.

Let path $t$ intersect cells $(k_{1},m_{1})$ and $(k_{2},m_{2})$ then ${\sf
PS}(t[k_{1},...,k_{2}])\leq{\sf PS}(t_{1}[k_{1},...,k_{2}])$;

  3. 3.

Let path $t$ intersect cell $(k_{1},m_{1})$ and $t$ intersect $t_{1}$ at row
$k_{2}$ then ${\sf PS}(t[k_{1},...,k_{2}-1])\leq{\sf
PS}(t_{1}[k_{1},...,k_{2}-1])$;

  4. 4.

Let path $t$ intersect cells $(k_{1},m_{1})$ and $(k_{2},m_{2})$, and ${\sf
PS}(t[k_{1},...,k_{2}-1])={\sf F}_{k_{1},m_{1}}-{\sf F}_{k_{2},m_{2}}$. Then
for any $k_{1}\leq k_{1}^{\prime}\leq k_{2}^{\prime}\leq k_{2}$ we get ${\sf
PS}(t[k_{1}^{\prime},...,k_{2}^{\prime}-1])={\sf
F}_{k_{1}^{\prime},t(k_{1}^{\prime})}-{\sf
F}_{k_{2}^{\prime},t(k_{2}^{\prime})}$;

  5. 5.

Let path $t$ intersect cells $(k_{1},m_{1})$ and $(k,m)$ for some $k>k_{1}$
and $0\leq m\leq{\textit{W}}-1$, then ${\sf PS}(t[k_{1},...,k-1])\leq{\sf
F}_{k_{1},m_{1}}-{\sf F}_{k,m}$.

###### Proof.

  1. 1.

Since $t_{1}$ defined by ${\sf F}$, then for any row $i\geq i_{1}$ by Note 4
we get ${\sf PS}(t_{1}[i,...])={\sf F}_{i,t_{1}(i)}$. Thus ${\sf
PS}(t_{1}[k_{1},...,k_{2}-1])={\sf PS}(t_{1}[k_{1},...)-{\sf
PS}(t_{1}[k_{2},...])={\sf F}_{k_{1},m_{1}}-{\sf F}_{k_{2},m_{2}}$.

  2. 2.

Suppose that ${\sf PS}(t[k_{1},...,k_{2}])>{\sf PS}(t_{1}[k_{1},...,k_{2}])$.

Let $t^{\prime}$ is concatenation with begining on cell $(k_{1},m_{1})$ such
that $t^{\prime}[k_{1},...,k_{2}]=t[k_{1},...,k_{2}]$ and
$t^{\prime}[k_{2}+1,...]=t_{1}[k_{2}+1,...]$. By Note 3 the $t^{\prime}$ is
path.

Then ${\sf F}_{k_{1},m_{1}}\geq{\sf PS}(t^{\prime})$ and the other side:
$\begin{array}[]{lll}{\sf PS}(t^{\prime})&={\sf PS}(t[k_{1},...,k_{2}])+{\sf
PS}(t_{1}[k_{2}+1,...])>\\\ &>{\sf PS}(t_{1}[k_{1},...,k_{2}])+{\sf
PS}(t_{1}[k_{2}+1,...])={\sf PS}(t_{1}[k_{1},...])={\sf
F}_{k_{1},m_{1}}\end{array}$

This contradiction proves statement 2.

  3. 3.

Let $t^{\prime}$ is concatenation of $t[k_{1},...,k_{2}-1]$ and
$t_{1}[k_{2},...]$. By Property 1 $t^{\prime}$ is path. Also $t^{\prime}$
intersects with cells $(k_{1},m_{1})$ and $(k_{2},m_{2})$. Then using Property
2.2 we get ${\sf PS}(t_{1}[{k_{1},...,k_{2}-1}])={\sf
PS}(t_{1}[k_{1},...,k_{2}])-{\sf g}_{k_{2},m_{2}}\geq{\sf
PS}(t^{\prime}[k_{1},...,k_{2}])-{\sf g}_{k_{2},m_{2}}={\sf
PS}(t[{k_{1},...,k_{2}-1}])$.

  4. 4.

Let $t_{2}$ is path defined by ${\sf F}_{k_{2},m_{2}}$. And $t^{\prime}$ is
concatenation of $t[k_{1},...,k_{2}-1]$ and $t_{2}[k_{2},...]$. Then by Note 3
$t^{\prime}$ is path, with sum ${\sf PS}(t^{\prime})={\sf
PS}(t[k_{1},...,k_{2}-1])+{\sf PS}(t_{2}[k_{2},...])={\sf
F}_{k_{1},m_{1}}-{\sf F}_{k_{2},m_{2}}+{\sf F}_{k_{2},m_{2}}={\sf
F}_{k_{1},m_{1}}$. I.e. $t^{\prime}$ defined by ${\sf F}_{k_{1},m_{1}}$.

Then using Property 2.1 we get ${\sf
PS}(t^{\prime}[k_{1}^{\prime},...,k_{2}^{\prime}-1])={\sf
F}_{k_{1}^{\prime},t^{\prime}(k_{1}^{\prime})}-{\sf
F}_{k_{2}^{\prime},t^{\prime}(k_{2}^{\prime})}$. Since
$t(k_{2})=t^{\prime}(k_{2})$ then
$t[k_{1}^{\prime},...,k_{2}^{\prime}]=t^{\prime}[k_{1}^{\prime},...,k_{2}^{\prime}]$
then ${\sf PS}(t[k_{1}^{\prime},...,k_{2}^{\prime}-1])={\sf
F}_{k_{1}^{\prime},t(k_{1}^{\prime})}-{\sf
F}_{k_{2}^{\prime},t(k_{2}^{\prime})}$.

  5. 5.

Let $b_{1}=\max\\{0,t(k-1)-1\\}$ and
$b_{2}=\min\\{t(k-1)+1,{\textit{W}}-1\\}$. Then $m\in\\{b_{1},...,b_{2}\\}$.

Let prove by induction on difference $k-k_{1}$

Base case:
If $k-k_{1}=1$ then ${\sf PS}(t[k_{1},...,k-1])={\sf PS}(t[k_{1}])={\sf
g}_{k_{1},m_{1}}={\sf g}_{k-1,t(k-1)}\leq\\\ \leq{\sf
g}_{k-1,t(k-1)}+\max_{j=b_{1},...,b_{2}}\\{{\sf F}_{k,j}\\}-{\sf F}_{k,m}={\sf
F}_{k_{1},m_{1}}-{\sf F}_{k,m}$.

Induction step:
Let $k-k_{1}>1$, and ${\sf PS}(t[k_{1},...,k-2])\leq{\sf F}_{k_{1},m_{1}}-{\sf
F}_{k-1,t(k-1)}$.

Then ${\sf PS}(t[k_{1},...,k-1])={\sf PS}(t[k_{1},...,k-2])+{\sf
g}_{k-1,t(k-1)}\leq\\\ \leq{\sf PS}(t[k_{1},...,k-2])+{\sf
g}_{k-1,t(k-1)}+\max_{j=b_{1},...,b_{2}}\\{{\sf F}_{k,j}\\}-{\sf F}_{k,m}=\\\
={\sf PS}(t[k_{1},...,k-2])+{\sf F}_{k-1,t(k-1)}-{\sf F}_{k,m}\leq({\sf
F}_{k_{1},m_{1}}-{\sf F}_{k-1,t(k-1)})+{\sf F}_{k-1,t(k-1)}-{\sf F}_{k,m}=\\\
={\sf F}_{k_{1},m_{1}}-{\sf F}_{k,m}$.

∎

######  Note 5.

${\sf l_{p}}(i)\leq{\sf r_{p}}(i)$ for each $i=0,...,{\textit{H}}-1$.

######  Note 6.

${\sf PS}({\sf l_{p}})={\sf F}_{0,0}$ and ${\sf PS}({\sf r_{p}})={\sf
F}_{0,{\textit{W}}-1}$.

######  Definition 10.

${\sf g_{l}}$ is grid defined for each $i=0,...,{\textit{H}}-1$ as:

${\sf g_{l}}_{i,j}=\begin{cases}-\infty&j={\sf
l_{p}}(i)+1,...,{\textit{W}}-1,\\\ {\sf g}_{i,j}&j=0,...,{\sf
l_{p}}(i).\end{cases}$

And ${\sf g_{r}}$ is grid defined for each $i=0,...,{\textit{H}}-1$ as:

${\sf g_{r}}_{i,j}=\begin{cases}{\sf g}_{i,j}&j={\sf
r_{p}}(i),...,{\textit{W}}-1,\\\ -\infty&j=0,...,{\sf r_{p}}(i)-1.\end{cases}$

######  Property 3.

For each $i=0,...,{\textit{H}}-1$ and $j\leq{\sf l_{p}}(i)$ we get ${\sf
F}_{i,j}({\sf g})={\sf F}_{i,j}({\sf g_{l}})$, and for $j\geq{\sf r_{p}}(i)$
we get ${\sf F}_{i,j}({\sf g})={\sf F}_{i,j}({\sf g_{r}})$.

###### Proof.

Due to ${\sf g}_{i,j}\geq{\sf g_{l}}_{i,j}$ for each $i$ and $j$, we get ${\sf
F}_{i,j}({\sf g})\geq{\sf F}_{i,j}({\sf g_{l}})$ for each $i$ and $j$.

Let $t$ is ${path}$ $defined$ $by$ ${\sf F}_{i_{1},j_{1}}({\sf g})$ for some
$i_{1}$ and $j_{1}\leq{\sf l_{p}}(i_{1})$, then ${\sf PS}(t)={\sf
F}_{i_{1},j_{1}}({\sf g})$.

Consider 2 cases:

  * •

If $t(i)\leq{\sf l_{p}}(i)$ for each $i$, then ${\sf F}_{i_{1},j_{1}}({\sf
g_{l}})\geq{\sf PS}(t)={\sf F}_{i_{1},j_{1}}({\sf g})$.

  * •

Let $i_{2}$ is lowest row such that $t(i_{2})>{\sf l_{p}}(i_{2})$ (i.e.
$i_{2}>i_{1}$). Then due to Property 1 a concatenation $t^{\prime}$ of ${\sf
l_{p}}[...,i_{2}-1]$ and $t[i_{2},...]$ is path.

Since $t$ defined by ${\sf F}({\sf g})$ then by Note 4 we get ${\sf
PS}(t[i_{2},...])={\sf F}_{i_{2},t(i_{2})}({\sf g})$. Since ${\sf l_{p}}$
defined by ${\sf F}({\sf g})$ then by Property 2.1 we get ${\sf PS}({\sf
l_{p}}[...,i_{2}-1])={\sf F}_{0,0}({\sf g})-{\sf F}_{i_{2},{\sf
l_{p}}(i_{2})}({\sf g})$.

Then ${\sf F}_{0,0}({\sf g})\geq{\sf PS}(t^{\prime})={\sf PS}({\sf
l_{p}}[...,i_{2}-1])+{\sf PS}(t[i_{2},...])={\sf F}_{0,0}({\sf g})-{\sf
F}_{i_{2},{\sf l_{p}}(i_{2})}({\sf g})+{\sf F}_{i_{2},t(i_{2})}({\sf g})$.
Thus ${\sf F}_{i_{2},{\sf l_{p}}(i_{2})}({\sf g})\geq{\sf
F}_{i_{2},t(i_{2})}({\sf g})$.

Consider concatenation $t^{\prime\prime}$ of $t[i_{1},...,i_{2}-1]$ and ${\sf
l_{p}}[i_{2},...]$. Then due to Property 1 the $t^{\prime\prime}$ is path.

Since ${\sf l_{p}}$ defined by ${\sf F}({\sf g})$, due to Note 4 we get ${\sf
PS}({\sf l_{p}}[i_{2},...])={\sf F}_{i_{2},{\sf l_{p}}(i_{2})}({\sf g})$. By
Property 2.1 we get ${\sf PS}(t[i_{1},...,i_{2}-1])={\sf F}_{i_{1},j_{1}}({\sf
g})-{\sf F}_{i_{2},t(i_{2})}({\sf g})$. Then
$\begin{array}[]{ll}{\sf PS}(t^{\prime\prime})&={\sf
PS}(t[i_{1},...,i_{2}{-}1])+{\sf PS}({\sf l_{p}}[i_{2},...])={\sf
F}_{i_{1},j_{1}}({\sf g})-{\sf F}_{i_{2},t(i_{2})}({\sf g})+{\sf
F}_{i_{2},{\sf l_{p}}(i_{2})}({\sf g})\geq\\\ &\geq{\sf F}_{i_{1},j_{1}}({\sf
g}).\end{array}$
By our choice of $t^{\prime}$ we get $t^{\prime\prime}(i)\leq{\sf l_{p}}(i)$
for each $i$. Then ${\sf F}_{i_{1},j_{1}}({\sf g_{l}})\geq{\sf
PS}(t^{\prime\prime})\geq{\sf F}_{i_{1},j_{1}}({\sf g})$.

Similarly we can proof that ${\sf F}_{i,j}({\sf g})={\sf F}_{i,j}({\sf
g_{r}})$. ∎

######  Property 4.

Let $0{\leq}i_{1}{<}i_{2}{\leq}{\textit{H}}{-}1$, and consider path $t$ from
cell $(i_{1},{\sf l_{p}}(i_{1}))$ to cell $(i_{2},{\sf l_{p}}(i_{2}))$, and
path $t^{\prime}$ from cell $(i_{1},{\sf r_{p}}(i_{1}))$ to cell $(i_{2},{\sf
r_{p}}(i_{2}))$. Then:

  1. 1.

Due to Property 2.2 and Note 6 we get ${\sf PS}(t)\leq{\sf PS}({\sf
l_{p}}[i_{1},...,i_{2}])$.
Similarly we get ${\sf PS}(t^{\prime})\leq{\sf PS}({\sf
r_{p}}[i_{1},...,i_{2}])$.

  2. 2.

Due to Property 4.1, leftmost of ${\sf l_{p}}$ and rigthmost of ${\sf r_{p}}$
we get implication:
if ${\sf PS}(t)={\sf PS}({\sf l_{p}}[i_{1},...,i_{2}])$ then $t(i)\geq{\sf
l_{p}}(i)$ for each $i=i_{1},...,i_{2}$;
if ${\sf PS}(t^{\prime})={\sf PS}({\sf r_{p}}[i_{1},...,i_{2}])$ then
$t^{\prime}(i)\leq{\sf r_{p}}(i)$ for each $i=i_{1},...,i_{2}$.

  3. 3.

If $t$ is ${\sf LP}$ path and ${\sf PS}(t)={\sf PS}({\sf
l_{p}}[i_{1},...,i_{2}])$, then by Property 4.2 we get $t={\sf
l_{p}}[i_{1},...,i_{2}]$.
Similarly, if $t^{\prime}$ is ${\sf RP}$ path and ${\sf PS}(t^{\prime})={\sf
PS}({\sf r_{p}}[i_{1},...,i_{2}])$, then $t^{\prime}={\sf
r_{p}}[i_{1},...,i_{2}]$.

  4. 4.

If $p$ is ${\sf LP}_{i_{1},{\sf l_{p}}(i_{1})}$ path and ${\sf PS}(p)={\sf
PS}({\sf l_{p}}[i_{1},...])$, then due to leftmost and maximum sum of ${\sf
l_{p}}$ we get $p={\sf l_{p}}[i_{1},...]$.
Similarly, if $p^{\prime}$ is ${\sf RP}_{i_{1},{\sf r_{p}}(i_{1})}$ path and
${\sf PS}(p^{\prime})={\sf PS}({\sf r_{p}}[i_{1},...])$, then $p^{\prime}={\sf
r_{p}}[i_{1},...]$.

######  Definition 11.

Let path $t$ with begining at cell ${(i,j)}$ and ends at $i^{\prime}$-th row.

If ${t(k)\leq{\sf l_{p}}(k)}$ for each ${k=i,...,i^{\prime}}$ then call $t$ as
${\sf LP}_{i,j}$ path.

If ${t(k)\geq{\sf r_{p}}(k)}$ for each ${k=i,...,i^{\prime}}$ then call $t$ as
${\sf RP}_{i,j}$ path.

######  Note 7.

If $t$ is ${\sf LP}$ path, and $t(i)={\sf r_{p}}(i)$, then ${\sf
l_{p}}(i)={\sf r_{p}}(i)$. If $t$ is ${\sf RP}$ path, and $t(i)={\sf
l_{p}}(i)$, then ${\sf l_{p}}(i)={\sf r_{p}}(i)$.

######  Note 8.

Let paths $t_{1}$,…, $t_{n}$ don’t intersect the path $t_{0}$, and all
$t_{1}$,…, $t_{n}$ are placed on the same side of $t_{0}$. And $t$ is
concatenation of $t_{1},...,t_{n}$ subpaths, such that $t$ is path. Then $t$
is path without intersection with any subpath of $t_{0}$.

######  Note 9.

Let $t_{1}$,…, $t_{n}$ are ${\sf RP}_{i_{1},t_{1}(i_{1})}$, …, ${\sf
RP}_{i_{n},t_{n}(i_{n})}$ paths respectively, and $t$ is concatenation of
$t_{1}$,…, $t_{n}$ subpaths, such that $t$ is path. Then $t$ is ${\sf
RP}_{i,j}$ path for some $i$ and $j\geq{\sf r_{p}}(i)$.

Let $t_{1}$,…, $t_{n}$ are ${\sf LP}_{i_{1},t_{1}(i_{1})}$, …, ${\sf
LP}_{i_{n},t_{n}(i_{n})}$ paths respectively, and $t$ is concatenation of
$t_{1}$,…, $t_{n}$ subpaths, such that $t$ is path. Then $t$ is ${\sf
LP}_{i,j}$ path for some $i$ and $j\leq{\sf l_{p}}(i)$.

######  Definition 12.

Let $t_{1}$ and $t_{2}$ are ${\sf LP}_{i,j_{1}}$ and ${\sf RP}_{i,j_{2}}$
PWOI, such that ${\sf PS}(t_{1})+{\sf PS}(t_{2})$ is maximum among all ${\sf
LP}_{i,j_{1}}$ and ${\sf RP}_{i,j_{2}}$ pairs of PWOI and ending at bottom
(BE), then we call this pair as pair with maximum sum, and denote as ${\sf
lrdtms}(i,j_{1},j_{2})$ pair ((l)eft and (r)ight (d)isjoint (t)racks with
(m)aximum (s)um).

######  Definition 13.

${\sf{M_{r}}}$ is table, where ${\sf{M_{r}}}(i,j)={\sf PS}(l)+{\sf PS}(r)$ for
any ${\sf lrdtms}(i,j,{\sf r_{p}}(i))$ pair $l$ and $r$. I.e.
${\sf{M_{r}}}(i,j)$ is maximum sum among all pairs of ${\sf LP}_{i,j}$ and
${\sf RP}_{i,{\sf r_{p}}(i)}$ PWOI and BE.

${\sf{M_{l}}}$ is table, where ${\sf{M_{l}}}(i,j)={\sf PS}(l)+{\sf PS}(r)$ for
any ${\sf lrdtms}(i,{\sf l_{p}}(i),j)$ pair $l$ and $r$.

######  Note 10.

For each row $i$ the ${\sf{M_{r}}}$ defined in columns $j\leq\min\\{{\sf
l_{p}}(i),{\sf r_{p}}(i)-1\\}$ only. For each row $i$ the ${\sf{M_{l}}}$
defined in columns $j\geq\max\\{{\sf l_{p}}(i)+1,{\sf r_{p}}(i)\\}$ only.

###  3.1 Linear search of ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$

######  Property 5.

Let $lt$ and $rt$ are ${\sf lrdtms}(i,j_{1},j_{2})$ pair, for some
$j_{1}\leq{\sf l_{p}}(i)$ and $j_{2}\geq{\sf r_{p}}(i)$.

  1. 1.

If $lt$ intersect ${\sf l_{p}}$ at 2 rows $i_{2}>i_{1}>i$, and $rt$ don’t
intersect ${\sf l_{p}}$ between these rows, then $lt[i_{1},...,i_{2}]={\sf
l_{p}}[i_{1},...,i_{2}]$.

  2. 2.

If $lt$ intersect ${\sf l_{p}}$ at row $i^{\prime}$, and $rt$ don’t intersect
${\sf l_{p}}$ after this row, then $lt[i^{\prime},...]={\sf
l_{p}}[i^{\prime},...]$.

###### Proof.

  1. 1.

Suppose that $lt[i_{1},...,i_{2}]\neq{\sf l_{p}}[i_{1},...,i_{2}]$.

If suppose that ${\sf PS}(lt[i_{1},...,i_{2}])={\sf PS}({\sf
l_{p}}[i_{1},...,i_{2}])$ then by Property 4.3 we get
$lt[i_{1},...,i_{2}]={\sf l_{p}}[i_{1},...,i_{2}]$ that contradicts to our
assumption. Thus, using Property 4.1, we get inequality ${\sf
PS}(lt[i_{1},...,i_{2}])<{\sf PS}({\sf l_{p}}[i_{1},...,i_{2}])$.

Since $lt$ is ${\sf LP}$ path then because of the intersection with ${\sf
l_{p}}$ on $i_{1}$ and $i_{2}$ we get $lt(i_{1})={\sf l_{p}}(i_{1})$ and
$lt(i_{2})={\sf l_{p}}(i_{2})$. Then consider concatenation $lt^{\prime}$:
$\begin{array}[]{lll}&lt^{\prime}[i,...,i_{1}-1]&=lt[i,...,i_{1}-1],\\\
&lt^{\prime}[i_{1},...,i_{2}]&={\sf l_{p}}[i_{1},...,i_{2}],\\\
&lt^{\prime}[i_{2}+1,...]&=lt[i_{2}+1,...].\end{array}$

By Note 3 the $lt^{\prime}[i_{1},...]$ is path. Then by Note 3 the
$lt^{\prime}$ is path. By Note 9 the $lt^{\prime}$ is ${\sf LP}_{0,0}$ path.
By Note 8 $lt^{\prime}$ don’t intersects with $rt$.

Consider relation between ${\sf PS}(lt)$ and ${\sf PS}(lt^{\prime})$:
$\begin{array}[]{lll}{\sf PS}(lt)&={\sf PS}(lt[i,...,i_{1}{-}1])+{\sf
PS}(lt[i_{1},...,i_{2}])&+{\sf PS}(lt[i_{2}{+}1,...])<\\\ &<{\sf
PS}(lt[i,...,i_{1}{-}1])+{\sf PS}({\sf l_{p}}[i_{1},...,i_{2}])&+{\sf
PS}(lt[i_{2}{+}1,...])={\sf PS}(lt^{\prime}).\end{array}$

Thus we get $lt^{\prime}$ and $rt$ are ${\sf LP}_{i,j_{1}}$ and ${\sf
RP}_{i,j_{2}}$ paths without intersection with sum ${\sf PS}(lt^{\prime})+{\sf
PS}(rt)>{\sf PS}(lt)+{\sf PS}(rt)$. That contradict to maximum sum of ${\sf
lrdtms}(i,j_{1},j_{2})$ pair $lt$ and $rt$.

  2. 2.

Suppose that $lt[i^{\prime},...]\neq{\sf l_{p}}[i^{\prime},...]$. Since $lt$
is ${\sf LP}$ path then because of the intersection with ${\sf l_{p}}$ on
$i^{\prime}$ we get $lt(i^{\prime})={\sf l_{p}}(i^{\prime})$ and
$lt[i^{\prime}+1,...]\neq{\sf l_{p}}[i^{\prime}+1,...]$.

Then consider concatenations $lt^{\prime}$ and $lt^{\prime\prime}$:
$\begin{array}[]{lllll}&lt^{\prime}[...,i^{\prime}]&=lt[...,i^{\prime}],&lt^{\prime}[i^{\prime}+1,...]&={\sf
l_{p}}[i^{\prime}+1,...]\\\ &lt^{\prime\prime}[...,i^{\prime}]&={\sf
l_{p}}[...,i^{\prime}],&lt^{\prime\prime}[i^{\prime}+1,...]&=lt[i^{\prime}+1,...].\end{array}$

By Note 3 the $lt^{\prime}$ and $lt^{\prime\prime}$ are paths. Then by Note 9
the $lt^{\prime}$ and $lt^{\prime\prime}$ are ${\sf LP}$ paths. By Note 8
$lt^{\prime}$ don’t intersects with $rt$.

Since $lt^{\prime\prime}[i^{\prime}+1,...]=lt[i^{\prime}+1,...]\neq{\sf
l_{p}}[i^{\prime}+1,...]$ then $lt^{\prime\prime}\neq{\sf l_{p}}$. Then due to
leftmost of ${\sf l_{p}}$ among all ${\sf LP}$ paths with maximum sum we get
${\sf PS}({\sf l_{p}})>{\sf PS}(lt^{\prime\prime})$. Then
${\sf PS}(lt[i^{\prime}{+}1,...])={\sf PS}(lt^{\prime\prime})-{\sf PS}({\sf
l_{p}}[...,i^{\prime}])<{\sf PS}({\sf l_{p}})-{\sf PS}({\sf
l_{p}}[...,i^{\prime}])={\sf PS}({\sf l_{p}}[i^{\prime}{+}1,...])$.

Then ${\sf PS}(lt)={\sf PS}(lt[...,i^{\prime}])+{\sf
PS}(lt[i^{\prime}+1,...])<{\sf PS}(lt[...,i^{\prime}])+{\sf
PS}(lpath[i^{\prime}+1,...])={\sf PS}(lt^{\prime})$.

Thus we get ${\sf LP}_{i,j_{1}}$ and ${\sf RP}_{i,j_{2}}$ paths $lt^{\prime}$
and $rt$ without intersections with sum ${\sf PS}(lt^{\prime})+{\sf
PS}(rt)>{\sf PS}(lt)+{\sf PS}(rt)$. That contradict to maximum sum of ${\sf
lrdtms}(i,j_{1},j_{2})$ pair $lt$ and $rt$.

∎

######  Property 6.

Let $lt$ and $rt$ are ${\sf lrdtms}(i,j_{1},j_{2})$ pair. Then for any
$i^{\prime}\geq i$ the pair $lt[i^{\prime},...]$ and $rt[i^{\prime},...]$ are
${\sf lrdtms}(i^{\prime},lt(i^{\prime}),rt(i^{\prime}))$ pair.

###### Proof.

By Note 8 the $lt[i^{\prime},...]$ don’t intersects with $rt[i^{\prime},...]$.
By Note 9 the $lt[i^{\prime},...]$ and $rt[i^{\prime},...]$ are
$LP_{i^{\prime},lt(i^{\prime})}$ and $RP_{i^{\prime},rt(i^{\prime})}$ paths
respectively.

Let $lmt$ and $rmt$ are ${\sf
lrdtms}(i^{\prime},lt(i^{\prime}),rt(i^{\prime}))$ pair. Suppose that ${\sf
PS}(lmt)+{\sf PS}(rmt)>{\sf PS}(lt[i^{\prime},...])+{\sf
PS}(rt[i^{\prime},...])$. Consider concatenations $lp$ and $rp$ such that:
$\begin{array}[]{lllll}&lp[i,...,i^{\prime}-1]&=lt[i,...,i^{\prime}-1],&lp[i^{\prime},...]&=lmt[i^{\prime},...],\\\
&rp[i,...,i^{\prime}-1]&=rt[i,...,i^{\prime}-1],&rp[i^{\prime},...]&=rmt[i^{\prime},...].\\\
\end{array}$
By Note 3 the $lp$ and $rp$ are paths. By Note 9 $lp$ is $LP_{i,j_{1}}$ path
and $rp$ is $RP_{i,j_{1}}$ path.

Since $lt[i,...,i^{\prime}-1]$ don’t intersects with $rt[i,...,i^{\prime}-1]$,
and $lmt[i^{\prime},...]$ don’t intersects with $rmt[i^{\prime},...]$, then
$lp$ don’t intersects with $rp$. Then due to maximum sum of $lt$ and $rt$ we
get ${\sf PS}(lp)+{\sf PS}(rp)\leq{\sf PS}(lt)+{\sf PS}(rt)$. But the other
side
$\begin{array}[]{ll}{\sf PS}(lp)+{\sf PS}(rp)&={\sf
PS}(lt[i,...,i^{\prime}-1])+{\sf PS}(lmt[i^{\prime},...])+{\sf
PS}(rt[i,...,i^{\prime}-1])+{\sf PS}(rmt[i^{\prime},...])>\\\ &>{\sf
PS}(lt[i,...,i^{\prime}-1])+{\sf PS}(lt[i^{\prime},...])+{\sf
PS}(rt[i,...,i^{\prime}-1])+{\sf PS}(rt[i^{\prime},...])=\\\ &={\sf
PS}(lt)+{\sf PS}(rt).\end{array}$
This contradiction proves that ${\sf PS}(lmt)+{\sf PS}(rmt)={\sf
PS}(lt[i^{\prime},...])+{\sf PS}(rt[i^{\prime},...])$.

Thus we get $LP_{i^{\prime},lt(i^{\prime})}$ and
$RP_{i^{\prime},rt(i^{\prime})}$ paths $lt[i^{\prime},...]$ and
$rt[i^{\prime},...]$ respectively without intersection with maximum sum. I.e.
$lt[i^{\prime},...]$ and $rt[i^{\prime},...]$ are ${\sf
lrdtms}(i^{\prime},lt(i^{\prime}),rt(i^{\prime}))$ pair. ∎

######  Property 7.

Let $lt$ and $rt$ are ${\sf lrdtms}(i,lt(i),rt(i)))$ pair, $lt[i,...,ri]$
don’t intersects with ${\sf l_{p}}[i,...,ri]$ and $rt(ri)={\sf l_{p}}(ri)$ for
some $i<ri$. Let $i<i^{\prime}<ri$ and ${\sf r_{p}}(i^{\prime})\leq
j^{\prime}\leq rt(i^{\prime})$. Consider ${\sf RP}_{i^{\prime},j^{\prime}}$
path $rt^{\prime}$ where $rt^{\prime}[ri,...]=rt[ri,...]$ and ${\sf
PS}(rt^{\prime}[i^{\prime},...,ri])={\sf
F}_{i^{\prime},rt^{\prime}(i^{\prime})}-{\sf F}_{ri,rt^{\prime}(ri)}+{\sf
g}_{ri,rt^{\prime}(ri)}$. Then $lt[i^{\prime},...]$ and $rt^{\prime}$ are
${\sf lrdtms}(i^{\prime},lt(i^{\prime}),j^{\prime})$ pair.

###### Proof.

Since $lt$ is ${\sf LP}_{i,lt(i)}$ path and don’t intersects with ${\sf
l_{p}}[i,...,ri]$, then $lt(k)<{\sf l_{p}}(k)\leq{\sf r_{p}}(k)\leq
rt^{\prime}(k)$ for each $k=i^{\prime},...,ri$. Since $lt$ don’t intersects
with $rt$, then by Note 8 the $lt[i^{\prime},...]$ don’t intersects with
$rt^{\prime}$.

Let denote $lt[i^{\prime},...]$ and $rt[i^{\prime},...]$ as $lT$ and $rT$
respectively. Consider ${\sf lrdtms}(i^{\prime},lt(i^{\prime}),j^{\prime})$
pair $lP$ and $rP$. Since $rP$ is ${\sf RP}_{i^{\prime},j^{\prime}}$ path and
$j^{\prime}\leq rt(i^{\prime})=rT(i^{\prime})$, then $rP$ intersects with $rT$
on some row $rI\leq ri$. Let $rI$ is first row of intersection of $rP$ and
$rT$. Then $rT$ don’t intersects with $lP$ before $rI$. Since $lT$ don’t
intersects with any of ${\sf RP}$ path before $ri$, then $lT$ don’t intersects
with $rP$ before $rI$.

Let $rP_{1}$ and $rP^{\prime}$ are concatenations:
$\begin{array}[]{lllll}&rT^{\prime}[i^{\prime},...,rI-1]&=rP[i^{\prime},...,rI-1],&rT^{\prime}[rI,...]&=rT[rI,...],\\\
&rP^{\prime}[i^{\prime},...,rI-1]&=rT[i^{\prime},...,rI-1],&rP^{\prime}[rI,...]&=rP[rI,...].\end{array}$
If $rP(rI)=rT(rI)$ then by Note 3 the $rT^{\prime}$ and $rP^{\prime}$ are
paths. If $rP(rI)\neq rT(rI)$ then $rP(rI)>rT(rI)$ then by Property 1 the
$rT^{\prime}$ and $rP^{\prime}$ are paths. Then by Note 9 $rT^{\prime}$ and
$rP^{\prime}$ are ${\sf RP}$ paths. Using Note 8 the $lP$ don’t intersects
with $rP^{\prime}$, and $lT$ don’t intersects with $rT^{\prime}$.

Consider relations of differences $d_{1}={\sf PS}(lP)-{\sf PS}(lT)$ and
$d_{2}={\sf PS}(rT[rI,...])-{\sf PS}(rP[rI,...])$:

  * •

$d_{1}>d_{2}$. We get ${\sf LP}_{i^{\prime},lt(i^{\prime})}$ and ${\sf
RP}_{i^{\prime},rt(i^{\prime})}$ paths $lP$ and $rP^{\prime}$ without
intersections with sum
$\begin{array}[]{ll}{\sf PS}(lP)+{\sf PS}(rP^{\prime})&=d_{1}+{\sf
PS}(lT)+{\sf PS}(rT[i^{\prime},...,rI-1])+{\sf PS}(rP[rI,...])=\\\
&=d_{1}+{\sf PS}(lT)+{\sf PS}(rT[i^{\prime},...,rI-1])+{\sf
PS}(rT[rI,...])-d_{2}>\\\ &>{\sf PS}(lT)+{\sf PS}(rT).\end{array}$
which conrtadicts to maximum of ${\sf PS}(lT)+{\sf PS}(rT)$ due to Property 6.

  * •

$d_{1}\leq d_{2}$. We get ${\sf LP}_{i^{\prime},lt(i^{\prime})}$ and ${\sf
RP}_{i^{\prime},j^{\prime}}$ paths $lT$ and $rT^{\prime}$ without
intersections with sum
$\begin{array}[]{ll}{\sf PS}(lT)+{\sf PS}(rT^{\prime})&={\sf
PS}(lP)-d_{1}+{\sf PS}(rP[i^{\prime},...,rI-1])+{\sf PS}(rT[rI,...])=\\\
&={\sf PS}(lP)-d_{1}+{\sf PS}(rP[i^{\prime},...,rI-1])+{\sf
PS}(rP[rI,...])+d_{2}\geq\\\ &\geq{\sf PS}(lP)+{\sf PS}(rP).\end{array}$
Inequality ${\sf PS}(lT)+{\sf PS}(rP_{1})>{\sf PS}(lP)+{\sf PS}(rP)$
conrtadicts the maximum of ${\sf PS}(lP)+{\sf PS}(rP)$ among all pairs of
${\sf LP}_{i^{\prime},lt(i^{\prime})}$ and ${\sf RP}_{i^{\prime},j^{\prime}}$
paths without intersections.

Thus we get one valid case $d_{1}=d_{2}$ with equation ${\sf PS}(lT)+{\sf
PS}(rT^{\prime})={\sf PS}(lP)+{\sf PS}(rP)$. I.e. $lT=lt[i^{\prime},...]$ and
$rT^{\prime}$ are ${\sf lrdtms}(i^{\prime},lt(i^{\prime}),j^{\prime})$ pair.
Since $rI\leq ri$ then $rT^{\prime}(ri)=rT(ri)=rt(ri)$.

Thus we get $RP_{i^{\prime},j^{\prime}}$ path $rT^{\prime}$ where
$rT^{\prime}[ri,...]=rt[ri,...]$. Using Properties 3 and 2.5 we get ${\sf
PS}(rT^{\prime}[i^{\prime},...,ri])\leq{\sf F}_{i^{\prime},j^{\prime}}-{\sf
F}_{ri,rT^{\prime}(ri)}+{\sf g}_{ri,rT^{\prime}(ri)}={\sf
F}_{i^{\prime},rt^{\prime}(i^{\prime})}-{\sf F}_{ri,rt^{\prime}(ri)}+{\sf
g}_{ri,rt^{\prime}(ri)}={\sf PS}(rt^{\prime}[i^{\prime},...,ri])$.

Then, using condition $rI\leq ri$, we get
$\begin{array}[]{ll}{\sf PS}(lt[i^{\prime},...])+{\sf PS}(rt^{\prime})&={\sf
PS}(lT)+{\sf PS}(rt^{\prime}[i^{\prime},...,ri])+{\sf
PS}(rt^{\prime}[ri+1,...])\geq\\\ &\geq{\sf PS}(lT)+{\sf
PS}(rT^{\prime}[i^{\prime},...,ri])+{\sf PS}(rt[ri+1,...])=\\\ &={\sf
PS}(lT)+{\sf PS}(rT^{\prime}[i^{\prime},...,ri])+{\sf PS}(rT[ri+1,...])={\sf
PS}(lT)+{\sf PS}(rT^{\prime}).\end{array}$

Thus we get that $lt[i^{\prime},...]$ and $rt^{\prime}$ are ${\sf
LP}_{i^{\prime},lt(i^{\prime})}$ and ${\sf RP}_{i^{\prime},j^{\prime}}$ paths
respectively without intersections and with maximum sum. I.e.
$lt[i^{\prime},...]$ and $rt^{\prime}$ are ${\sf
lrdtms}(i^{\prime},lt(i^{\prime}),j^{\prime})$ pair. ∎

######  Property 8.

Let $lt$ and $rt$ are ${\sf lrdtms}(i-1,{\sf l_{p}}(i-1),j)$ pair, where
$j>{\sf r_{p}}(i-1)$. And $lt(i)<{\sf l_{p}}(i)$, $rt(i)>{\sf r_{p}}(i)$.
Then:

  1. 1.

Exist $ri>i$ such that $rt(ri)={\sf l_{p}}(ri)$, and $lt(k)<{\sf l_{p}}(k)$
for each $k=i,...,ri$;

  2. 2.

Consider concatenation $rt^{\prime}$ of ${\sf r_{p}}[i,...,ri{-}1]$ and
$rt[ri,...]$ (i.e. $rt^{\prime}[...,ri]={\sf r_{p}}[i,...,ri]$). Then
$lt[i,...]$ and $rt^{\prime}$ are ${\sf lrdtms}(i,lt(i),{\sf r_{p}}(i))$ pair;

  3. 3.

${\sf PS}(rt[i{-}1,...,ri])={\sf F}_{i{-}1,rt(i{-}1)}-{\sf F}_{ri,rt(ri)}+{\sf
g}_{ri,rt(ri)}$. And ${\sf PS}(rt[i,...,ri{-}1])={\sf F}_{i,rt(i)}-{\sf
F}_{ri,rt(ri)}$ by Property 2.1;

  4. 4.

Let $b_{1}=\max\\{0,{\sf l_{p}}(i-1)-1\\},b_{2}=\min\\{{\sf l_{p}}(i-1)+1,{\sf
l_{p}}(i)-1\\}$ and
$b_{3}=\max\\{{\sf r_{p}}(i)+1,j-1\\},b_{4}=\min\\{j+1,{\textit{W}}-1\\}$ then

${\sf PS}(lt[i,...])+{\sf
PS}(rt[i,...])=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}.$

###### Proof.

  1. 1.

Suppose that $rt$ don’t intersect ${\sf l_{p}}$ after $(i{-}1)$-th row. Then
due to Property 5.2 we get $lt[i-1,...]={\sf l_{p}}[i-1,...]$ that contradicts
with condition $lt(i)<{\sf l_{p}}(i)$. I.e. $rt$ intersect ${\sf l_{p}}$ after
$(i-1)$-th row.

Let $ri\geq i$ such that $rt(ri)={\sf l_{p}}(ri)$, and $rt(k)\neq{\sf
l_{p}}(k)$ for each $k=i-1,...,ri-1$.

Suppose that $lt$ intersects with ${\sf l_{p}}$ on row $li$ between $i$ and
$ri$. Since $lt(i{-}1)={\sf l_{p}}(i{-}1)$, then due to Property 5 we get
$lt[i{-}1,...,li]={\sf l_{p}}[i{-}1,...,li]$ that contradicts with $lt(i)<{\sf
l_{p}}(i)$.

Thus $lt(k)\neq{\sf l_{p}}(k)$ for each $k=i,...,ri$. Then because of $lt$ is
${\sf LP}$ path then $lt(k)<{\sf l_{p}}(k)$ for each $k=i,...,ri$. Since ${\sf
r_{p}}(i)<rt(i)$ then $ri>i$.

  2. 2.

Since $rt(ri)={\sf l_{p}}(ri)$ then using Note 7 we get
$rt^{\prime}[i,...,ri]={\sf r_{p}}[i,...,ri]$. Due to Note 3 the $rt^{\prime}$
is path. By Note 9 the $rt^{\prime}$ is ${\sf RP}_{i,j}$ path.

Since ${\sf r_{p}}$ defined by ${\sf F}$ then ${\sf
PS}(rt^{\prime}[i,...,ri])={\sf PS}({\sf r_{p}}[i,...,ri])={\sf
F}_{i,rt^{\prime}(i)}-{\sf F}_{ri,rt^{\prime}(ri)}+{\sf
g}_{ri,rt^{\prime}(ri)}$. Then due to Property 7 the $lt[i,...]$ and
$rt^{\prime}$ are ${\sf lrdtms}(i,lt(i),rt^{\prime}(i))$ pair. Since
$rt^{\prime}(i)={\sf r_{p}}(i)$ we get proof of statement 2.

  3. 3.

Since ${\sf l_{p}}(i-1)=lt(i-1)$ and $lt$ is $LP$ path then by Property 4.1
${\sf PS}({\sf l_{p}}[i-1,...])\geq{\sf PS}(lt)$. Since ${\sf l_{p}}(i)<lt(i)$
then ${\sf l_{p}}[i-1,...]\neq lt[i-1,...]$. Then since ${\sf
l_{p}}(i-1)=lt(i-1)$ and $lt$ is $LP$ by Property 4.4 we get ${\sf PS}({\sf
l_{p}}[i-1,...])>{\sf PS}(lt[i-1,...])$.

Consider ${\sf RP}_{i-1,j}$ path $rt^{\prime\prime}$ defined by ${\sf
F}_{i-1,j}({\sf g_{r}})$. Then ${\sf PS}(rt)\leq{\sf F}_{i-1,j}({\sf
g_{r}})={\sf PS}(rt^{\prime\prime})$.

In case when $rt^{\prime}(k)<rt^{\prime\prime}(k)$ for each $k\geq i-1$ we get
${\sf l_{p}}[i-1,...]$ and $rt^{\prime\prime}$ are ${\sf LP}_{i-1,{\sf
l_{p}}(i-1)}$ and ${\sf RP}_{i-1,j}$ paths without intersections and with sum
${\sf PS}({\sf l_{p}}[i-1,...])+{\sf PS}(rt^{\prime\prime})>{\sf PS}(lt)+{\sf
PS}(rt)$ that contradict to maximum sum of $lt$ and $rt$. I.e. this case
impossible.

Then $rt^{\prime}(i^{\prime})\geq rt^{\prime\prime}(i^{\prime})$ for some
$i^{\prime}>i-1$. WLOG we can assume that
$rt^{\prime}(k)<rt^{\prime\prime}(k)$ for each $k=i-1,...,i^{\prime}-1$.

Let $ri^{\prime}>ri$ such that ${\sf r_{p}}(ri^{\prime})<rt(ri^{\prime})$ and
${\sf r_{p}}(k)=rt(k)$ for each $k=ri,...,ri^{\prime}-1$. I.e. using Property
8.1 we get $lt(k)<{\sf r_{p}}(k)$ for each $k=i,...,ri^{\prime}-1$. And since
$rt^{\prime\prime}(i{-}1)=j>{\sf r_{p}}(i{-}1)\geq{\sf l_{p}}(i{-}1)$ then
$lt$ don’t intersects with $rt^{\prime\prime}[i{-}1,...,ri^{\prime}{-}1]$. If
$rt[ri,...]={\sf r_{p}}[ri,...]$ then we can assume that
$ri^{\prime}={\textit{H}}$ and ${\sf F}_{{\textit{H}},k}=0$ for each
$k=0,...,{\textit{W}}-1$.

If $i^{\prime}<ri^{\prime}$ then
$rt^{\prime\prime}(i^{\prime})=rt^{\prime}(i^{\prime})={\sf
r_{p}}(i^{\prime})$ then due to Property 4.4 we get
$rt^{\prime\prime}[i^{\prime},...]={\sf r_{p}}[i^{\prime},...]$. Then
$rt^{\prime\prime}(ri^{\prime}-1)={\sf
r_{p}}(ri^{\prime}-1)=rt(ri^{\prime}-1)$.

Then due to Properties 2.3 we get ${\sf
PS}(rt^{\prime\prime}[i-1,...,ri^{\prime}-2])\geq{\sf
PS}(rt[i{-}1,...,ri^{\prime}{-}2])$.

Suppose that ${\sf PS}(rt^{\prime\prime}[i-1,...,ri^{\prime}-2])>{\sf
PS}(rt[i-1,...,ri^{\prime}-2])$. Then consider concatenation $rp$ of
$rt^{\prime\prime}[i-1,...,ri^{\prime}-2]$ and $rt[ri^{\prime}-1,...]$. Since
$rt^{\prime\prime}(ri^{\prime}-1)=rt(ri^{\prime}-1)$ then by Property 1 the
$rp$ is path. By Note 9 the $rp$ is ${\sf RP}$ path. By Note 8 the $lt$ don’t
intersects with $rp$. Thus $lt$ and $rp$ are ${\sf LP}_{i-1,{\sf l_{p}}(i-1)}$
and ${\sf RP}_{i-1,j}$ paths without intersection with sum ${\sf PS}(lt)+{\sf
PS}(rp)={\sf PS}(lt)+{\sf PS}(rt^{\prime\prime}[i-1,...,ri^{\prime}-2])+{\sf
PS}(rt[ri^{\prime}-1,...])>{\sf PS}(lt)+{\sf PS}(rt)$ that contradict to
maximum sum of $lt$ and $rt$.

Thus ${\sf PS}(rt[i-1,...,ri^{\prime}-2])={\sf
PS}(rt^{\prime\prime}[i-1,...,ri^{\prime}-2])$. Then using Property 2.4 and
$ri\leq ri^{\prime}-1$ we get ${\sf PS}(rt[i,...,ri-1])={\sf F}_{i,rt(i)}-{\sf
F}_{ri,rt(ri)}$ that proves this case.

It remains to consider case $ri^{\prime}\leq i^{\prime}$. Then
$i<ri<ri^{\prime}\leq i^{\prime}$.

Let $rt_{1}$ is concatenation of $rt^{\prime\prime}[i-1,...,i^{\prime}-1]$ and
$rt^{\prime}[i^{\prime},...]$. By Property 1 the $rt_{1}$ is path. By Note 9
the $rt_{1}$ is ${\sf RP}$ path. Since $lt(k)<rt^{\prime}(k)\leq
rt^{\prime\prime}(k)$ for each $k=i,...,i^{\prime}-1$ and
$lt(i-1)<j=rt^{\prime\prime}(i-1)$ then using Note 8 the $lt$ don’t intersects
with $rt_{1}$.

Since $ri<ri^{\prime}\leq i^{\prime}$ then
$rt^{\prime}[i^{\prime},...]=rt[i^{\prime},...]$ then $rt_{1}$ intersects $rt$
at row $i^{\prime}$. Using Property 2.3 we get ${\sf
PS}(rt^{\prime\prime}[i-1,...,i^{\prime}-1])\geq{\sf
PS}(rt[i-1,...,i^{\prime}-1])$.

If ${\sf PS}(rt^{\prime\prime}[i-1,...,i^{\prime}-1])>{\sf
PS}(rt[i-1,...,i^{\prime}-1])$ then ${\sf PS}(rt_{1})={\sf
PS}(rt^{\prime\prime}[i-1,...,i^{\prime}-1])+{\sf
PS}(rt^{\prime}[i^{\prime},...])\geq{\sf PS}(rt[i-1,...,i^{\prime}-1])+{\sf
PS}(rt[i^{\prime},...])={\sf PS}(rt)$. Then $lt$ and $rt_{1}$ are ${\sf
LP}_{i-1,lt(i-1)}$ and ${\sf RP}_{i-1,j}$ paths without intersection and with
sum ${\sf PS}(lt)+{\sf PS}(rt_{1})>{\sf PS}(lt)+{\sf PS}(rt)$ that contradict
to maximum sum of $lt$ and $rt$.

Then ${\sf PS}(rt^{\prime\prime}[i-1,...,i^{\prime}-1])={\sf
PS}(rt[i-1,...,i^{\prime}-1])$.

Let $rt_{2}$ is concatenation of $rt[i-1,...,i^{\prime}-1]$ and
$rt^{\prime\prime}[i^{\prime},...]$. Since $rt^{\prime\prime}$ intersects $rt$
at row $i^{\prime}$ then by Property 1 we get that $rt_{2}$ is path. Then
${\sf PS}(rt_{2})={\sf PS}(rt[i-1,...,i^{\prime}-1])+{\sf
PS}(rt^{\prime\prime}[i^{\prime},...])={\sf PS}(rt^{\prime\prime})={\sf
F}_{i-1,j}$. Thus using Note 1 we get that $rt_{2}$ defined by ${\sf
F}_{i-1,j}$.

Since $ri<i^{\prime}$ then $rt_{2}(ri)=rt(ri)$ and $rt_{2}(i)=rt(i)$. Then
using Property 2.1 and $ri<i^{\prime}$ we get ${\sf PS}(rt[i-1,...,ri])={\sf
PS}(rt_{2}[i-1,...,ri])={\sf F}_{i-1,rt_{2}(i-1)}-{\sf F}_{ri,rt_{2}(ri)}+{\sf
g}_{ri,rt(ri)}={\sf F}_{i-1,rt(i-1)}-{\sf F}_{ri,rt(ri)}+{\sf g}_{ri,rt(ri)}$.

  4. 4.

The set $\\{b_{1},...,b_{2}\\}$ are all possible columns which can be
intersected at row $i$ by ${\sf LP}_{i-1,{\sf l_{p}}(i-1)}$ path $t_{1}$ with
restriction $t_{1}(i)<{\sf l_{p}}(i)$. The set $\\{b_{3},...,b_{4}\\}$ are all
possible columns which can be reached at row $i$ by ${\sf RP}_{i-1,j}$ path
$t_{2}$ with restriction $t_{2}(i)>{\sf r_{p}}(i)$. Since ${\sf
r_{p}}(i)+1\leq{\textit{W}}-1$, ${\sf l_{p}}(i-1)\leq{\sf l_{p}}(i)$ and ${\sf
l_{p}}(i)-1\geq 0$ then $b_{1}\leq b_{2}$ and $b_{3}\leq b_{4}$ i.e. these
sets are not empty.

By Property 8.3 we get ${\sf PS}(rt[i,...,ri-1])={\sf F}_{i,rt(i)}-{\sf
F}_{ri,rt(ri)}$. Since $lt[i,...]$ and $rt^{\prime}[i,...]$ are ${\sf
lrdtms}(i,lt(i),{\sf r_{p}}(i))$ pair and $lt(i-1)={\sf l_{p}}(i-1)$ then
${\sf PS}(lt[i,...])+{\sf
PS}(rt^{\prime}[i,...])=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}$.
Recall that ${\sf PS}(rt^{\prime}[i,...,ri-1])={\sf PS}({\sf
r_{p}}[i,...,ri-1])={\sf F}_{i,rt^{\prime}(i)}-{\sf F}_{ri,rt^{\prime}(ri)}$
and $rt^{\prime}(ri)=rt(ri)={\sf r_{p}}(ri)$. Then
$\begin{array}[]{ll}{\sf PS}(lt[i,...])+{\sf PS}(rt[i,...])={\sf
PS}(lt[i,...])+{\sf F}_{i,rt(i)}-{\sf F}_{ri,rt(ri)}+{\sf PS}(rt[ri,...])=\\\
={\sf PS}(lt[i,...])+{\sf F}_{i,rt(i)}-{\sf F}_{i,rt^{\prime}(i)}+{\sf
PS}(rt^{\prime}[i,...,ri-1])+{\sf PS}(rt[ri,...])=\\\ ={\sf
PS}(lt[i,...])+{\sf F}_{i,rt(i)}-{\sf F}_{i,rt^{\prime}(i)}+{\sf
PS}(rt^{\prime}[i,...])=\\\ ={\sf PS}(lt[i,...])+{\sf
PS}(rt^{\prime}[i,...])+{\sf F}_{i,rt(i)}-{\sf F}_{i,{\sf
r_{p}}(i)}.\end{array}$

Let prove that ${\sf F}_{i,rt(i)}=\max_{k=b_{3},...,b_{4}}\\{{\sf
F}_{i,k}\\}$. Since ${\sf r_{p}}(i)<rt(i)$ then
$rt(i)\in\\{b_{3},...,b_{4}\\}$ then ${\sf
F}_{i,rt(i)}\leq\max_{k=b_{3},...,b_{4}}\\{{\sf F}_{i,k}\\}$.

Suppose that exists $j^{\prime}\in\\{b_{3},...,b_{4}\\}$ such that ${\sf
F}_{i,j^{\prime}}>{\sf F}_{i,rt(i)}$. Consider ${\sf RP}_{i,j^{\prime}}$ path
$rt_{2}$ defined by ${\sf F}_{i,j^{\prime}}$. Let $rt_{2}^{\prime}$ is
concatenation of $rt[i-1]$ and $rt_{2}[i,...]$. Due to $\max\\{j-1,{\sf
r_{p}}(i)\\}\leq b_{3}\leq b_{4}\leq\min\\{j+1,{\textit{W}}-1\\}$ then
$rt_{2}^{\prime}$ is ${\sf RP}_{i-1,j}$ path.

If $rt^{\prime}(k)\leq rt_{2}(k)$ for each $k\geq i$ then $lt$ and
$rt_{2}^{\prime}$ are ${\sf lrdtms}(i-1,{\sf l_{p}}(i-1),j)$ pair with sum
${\sf PS}(lt)+{\sf PS}(rt_{2}^{\prime})={\sf PS}(lt)+{\sf
F}_{i,j^{\prime}}+{\sf g}_{i-1,j}>{\sf PS}(lt)+{\sf F}_{i,rt(i)}+{\sf
g}_{i-1,j}\geq{\sf PS}(lt)+{\sf PS}(rt)$. That contradict to maximum sum of
$lt$ and $rt$.

Then let $i_{2}\geq i$ such that $rt^{\prime}(i_{2})>rt_{2}^{\prime}(i_{2})$
and $rt^{\prime}(k)\leq rt_{2}^{\prime}(k)$ for each $k=i{-}1,...,i_{2}{-}1$.
Consider concatenation $rt_{2}^{\prime\prime}$ of
$rt_{2}^{\prime}[i-1,...,i_{2}-1]$ and $rt^{\prime}[i_{2},...]$. By Property 1
the $rt_{2}^{\prime\prime}$ is path. By Note 9 the $rt_{2}^{\prime\prime}$ is
${\sf RP}_{i-1,j}$ path. By Note 8 the $rt_{2}^{\prime\prime}$ don’t
intersects with $lt$.

If $i_{2}\geq ri$ then
$rt_{2}^{\prime\prime}(i_{2})=rt^{\prime}(i_{2})=rt(i_{2})$ then using
Property 2.3
${\sf PS}(lt)+{\sf PS}(rt_{2}^{\prime\prime})={\sf PS}(lt)+{\sf
F}_{i,j^{\prime}}-{\sf F}_{i_{2},rt_{2}^{\prime\prime}(i_{2})}+{\sf
PS}(rt[i_{2},...])+{\sf g}_{i-1,j}>\\\ >{\sf PS}(lt)+{\sf F}_{i,rt(i)}-{\sf
F}_{i_{2},rt(i_{2})}+{\sf PS}(rt[i_{2},...])+{\sf g}_{i-1,j}\geq{\sf
PS}(lt)+{\sf PS}(rt[i,...])+{\sf g}_{i-1,j}=\\\ ={\sf PS}(lt)+{\sf PS}(rt)$.
That contradict to maximum sum of $lt$ and $rt$.

Then $i_{2}<ri$. Due to ${\sf PS}(rt^{\prime}[i_{2},...,ri-1])={\sf PS}({\sf
r_{p}}[i_{2},...,ri-1])={\sf F}_{i_{2},{\sf r_{p}}(i_{2})}-{\sf F}_{ri,{\sf
r_{p}}(ri)}={\sf F}_{i_{2},{\sf r_{p}}(i_{2})}-{\sf F}_{ri,rt(ri)}$ we get
${\sf PS}(lt)+{\sf PS}(rt_{2}^{\prime\prime})={\sf PS}(lt)+{\sf
PS}(rt_{2}^{\prime}[i-1,...,i_{2}-1])+{\sf
PS}(rt^{\prime}[i_{2},...,ri-1])+{\sf PS}(rt^{\prime}[ri,...])=\\\ ={\sf
PS}(lt)+{\sf g}_{i-1,j}+{\sf F}_{i,j^{\prime}}-{\sf F}_{i_{2},{\sf
r_{p}}(i_{2})}+{\sf PS}({\sf r_{p}}[i_{2},...,ri-1])+{\sf PS}(rt[ri,...])>\\\
>{\sf PS}(lt)+{\sf g}_{i-1,j}+{\sf F}_{i,rt(i)}-{\sf F}_{ri,rt(ri)}+{\sf
PS}(rt[ri,...])=\\\ ={\sf PS}(lt)+{\sf g}_{i-1,j}+{\sf
PS}(rt[i,...,ri-1])+{\sf PS}(rt[ri,...])={\sf PS}(lt)+{\sf g}_{i-1,j}+{\sf
PS}(rt[i,...])=\\\ ={\sf PS}(lt)+{\sf PS}(rt)$.
That contradict to maximum sum of $lt$ and $rt$.

Thus ${\sf F}_{i,rt(i)}=\max_{k=b_{3},...,b_{4}}\\{{\sf F}_{i,k}\\}$. Then
${\sf PS}(lt[i,...])+{\sf PS}(rt^{\prime}[i,...])+{\sf F}_{i,rt(i)}-{\sf
F}_{i,{\sf r_{p}}(i)}=\\\
=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}.$

∎

Property 8 divided into 4 key notes, where each next note depends on previous.
Property 8.3 tells that $rt[i-1,...,ri]$ is subpath of some path defined by
${\sf F}_{i-1,rt(i-1)}$.

Property 8.4 tells that, if we will swap the tails of $rt[i,...]$ and ${\sf
r_{p}}[i,...]$ at row $ri$, then we get $rt^{\prime}$ (with head of ${\sf
r_{p}}$ and tail of $rt$) for which the difference between ${\sf
PS}(rt^{\prime}[i,...])$ and ${\sf PS}(rt[i,...])$ is the difference between
${\sf F}_{i,{\sf r_{p}}(i)}$ and ${\sf F}_{i,rt(i)}$.

Property 8.4 is main property that allows to find ${\sf{M_{l}}}$ and
${\sf{M_{r}}}$ in linear time, using DPM.

######  Property 9.

Let $lt$ and $rt$ are ${\sf lrdtms}(i-1,{\sf l_{p}}(i-1),j)$ pair. And let
$\max\\{0,{\sf l_{p}}(i-1)-1\\}\leq b_{1}\leq b_{2}\leq\min\\{{\sf
l_{p}}(i-1)+1,{\sf l_{p}}(i),{\sf r_{p}}(i)-1\\}$ and
$\max\\{{\sf l_{p}}(i)+1,{\sf r_{p}}(i),j-1\\}\leq b_{3}\leq
b_{4}\leq\min\\{j+1,{\textit{W}}-1\\}$. Then

${\sf PS}(lt[i,...])+{\sf
PS}(rt[i,...])\geq\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}.$

###### Proof.

Denote $lt[i,...]$ as $lt^{-}$ and $rt[i,...]$ as $rt^{-}$. And suppose that
${\sf PS}(lt^{-})+{\sf PS}(rt^{-})<{\sf{M_{r}}}(i,k_{1})+{\sf
F}_{i,k_{2}}-{\sf F}_{i,{\sf r_{p}}(i)}$ for some
$k_{1}\in\\{b_{1},...,b_{2}\\}$ and $k_{2}\in\\{b_{3},...,b_{4}\\}$.

Let $lt^{\prime}$ and $rt^{\prime}$ are ${\sf lrdtms}(i,k_{1},{\sf r_{p}}(i))$
pair. Then ${\sf PS}(lt^{\prime})+{\sf
PS}(rt^{\prime})={\sf{M_{r}}}(i,k_{1})$.

The set $\\{b_{1},...,b_{2}\\}$ is set of all columns which can be reached by
${\sf LP}_{i-1,{\sf l_{p}}(i-1)}$ path at row $i$ except column ${\sf
r_{p}}(i)$. Then concatenation $lt^{\prime+}$ of $lt[i-1]$ and $lt^{\prime}$
is ${\sf LP}_{i-1,lt(i-1)}$ path. Then by definition of ${\sf F}_{i-1,{\sf
l_{p}}(i-1)}$ and ${\sf l_{p}}$ we get ${\sf F}_{i,k_{1}}\leq{\sf F}_{i,{\sf
l_{p}}(i)}$. Since $rt^{\prime}(i)={\sf r_{p}}(i)$ then concatenation
$rt^{\prime+}$ of ${\sf r_{p}}[i-1]$ and $rt^{\prime}$ is ${\sf RP}_{i-1,{\sf
r_{p}}(i-1)}$ path.

Consider ${\sf RP}_{i,k_{2}}$ path $rt^{\prime\prime}$ defined by ${\sf
F}_{i,k_{2}}({\sf g_{r}})={\sf F}_{i,k_{2}}$. The set $\\{b_{3},...,b_{4}\\}$
is set of all columns which can be reached by ${\sf RP}(i-1,j)$ path at row
$i$ except column ${\sf l_{p}}(i)$. Then concatenation $rt^{\prime\prime+}$ of
$rt[i-1]$ and $rt^{\prime\prime}$ is ${\sf RP}_{i-1,j}$ path. By definition
${\sf PS}(lt)+{\sf PS}(rt)={\sf{M_{l}}}(i-1,j)\geq{\sf PS}(lt^{\prime+})+{\sf
PS}(rt^{\prime\prime+})$ then ${\sf PS}(lt^{-})+{\sf PS}(rt^{-})\geq{\sf
PS}(lt^{\prime})+{\sf PS}(rt^{\prime\prime})$.

If ${\sf r_{p}}(k)<rt^{\prime\prime}(k)$ for each $k\geq i$ then ${\sf
l_{p}}[i-1,...]$ don’t intersect $rt^{\prime\prime+}$ due to ${\sf
l_{p}}(i-1)<j=rt^{\prime\prime+}(i-1)$. Then by definition
$\begin{array}[]{ll}{\sf PS}(lt)+{\sf PS}(rt)={\sf{M_{l}}}(i-1,j)\geq{\sf
PS}({\sf l_{p}}[i-1,...])+{\sf PS}(rt^{\prime\prime+})={\sf F}_{i-1,{\sf
l_{p}}(i-1)}+{\sf g}_{i-1,j}+{\sf F}_{i,k_{2}}.\end{array}$
Then ${\sf PS}(lt^{-})+{\sf PS}(rt^{-})\geq{\sf F}_{i,{\sf l_{p}}(i)}+{\sf
F}_{i,k_{2}}\geq{\sf F}_{i,k_{1}}+{\sf F}_{i,k_{2}}\geq{\sf
PS}(lt^{\prime})+{\sf F}_{i,k_{2}}$. Since $rt^{\prime+}(i-1)={\sf
r_{p}}(i-1)$ then ${\sf PS}(rt^{\prime+})\leq{\sf F}_{i-1,{\sf r_{p}}(i-1)}$
then ${\sf PS}(rt^{\prime})\leq{\sf F}_{i,{\sf r_{p}}(i)}$. Then
$\begin{array}[]{ll}{\sf PS}(lt^{\prime})+{\sf F}_{i,k_{2}}\geq{\sf
PS}(lt^{\prime})+{\sf F}_{i,k_{2}}+{\sf PS}(rt^{\prime})-{\sf F}_{i,{\sf
r_{p}}(i)}={\sf{M_{r}}}(i,k_{1})+{\sf F}_{i,k_{2}}-{\sf F}_{i,{\sf
r_{p}}(i)}\end{array}$.

Thus ${\sf PS}(lt^{-})+{\sf PS}(rt^{-})\geq{\sf{M_{r}}}(i,k_{1})+{\sf
F}_{i,k_{2}}-{\sf F}_{i,{\sf r_{p}}(i)}$. That contradicts to our assumption.

Then exists $ri\geq i-1$ such that $rt^{\prime\prime}(ri)={\sf r_{p}}(ri)$.
Then, due to ${\sf r_{p}}(i)=rt^{\prime}(i)$, exists
$i^{\prime}\in\\{i,...,ri\\}$ such that $rt^{\prime}(i^{\prime})\geq
rt^{\prime\prime}(i^{\prime})$. WLOG we can assume that
$rt^{\prime}(k)<rt^{\prime\prime}(k)$ for each $k=i,...,i^{\prime}-1$ when
$i^{\prime}>i$. Then $lt^{\prime}$ don’t intersect
$rt^{\prime\prime}[...,i^{\prime}-1]$. If $i^{\prime}=i$ then assume that
$rt^{\prime\prime}[...,i^{\prime}-1]$ and $rt^{\prime}[...,i^{\prime}-1]$ is
empty paths.

Consider concatenation $rt_{1}$ of $rt^{\prime\prime+}[...,i^{\prime}-1]$ and
$rt^{\prime}[i^{\prime},...]$. By Property 1 the $rt_{1}$ is path. By Note 9
the $rt_{1}[i,...]$ is ${\sf RP}_{i,k_{2}}$ path. By Note 8
$lt^{\prime+}[i,...]$ don’t intersect $rt_{1}[i,...]$.

Let $rt_{2}$ is concatenation of $rt^{\prime+}[...,i^{\prime}-1]$ and
$rt^{\prime\prime}[i^{\prime},...]$. By Property 1 the $rt_{2}$ is path. Using
Prperty 4.1 we get ${\sf PS}(rt_{2}[i,...])\leq{\sf PS}({\sf
r_{p}}[i,...])={\sf F}_{i,{\sf r_{p}}(i)}$. Then
$\begin{array}[]{ll}{\sf PS}(rt_{1}[i,...])&={\sf PS}(rt^{\prime})+{\sf
PS}(rt^{\prime\prime})-{\sf PS}(rt_{2}[i,...])={\sf PS}(rt^{\prime})+{\sf
F}_{i,k_{2}}-{\sf PS}(rt_{2}[i,...])\geq\\\ &\geq{\sf PS}(rt^{\prime})+{\sf
F}_{i,k_{2}}-{\sf F}_{i,{\sf r_{p}}(i)}.\end{array}$

Thus $lt^{\prime+}[i,...]$ and $rt_{1}[i,...]$ are ${\sf LP}_{i,k_{1}}$ and
${\sf RP}_{i,k_{2}}$ paths without intersections and with sum
$\begin{array}[]{ll}{\sf PS}(lt^{\prime+}[i,...])+{\sf
PS}(rt_{1}[i,...])&\geq{\sf PS}(lt^{\prime})+{\sf PS}(rt^{\prime})+{\sf
F}_{i,k_{2}}-{\sf F}_{i,{\sf r_{p}}(i)}={\sf{M_{r}}}(i,k_{1})+{\sf
F}_{i,k_{2}}-{\sf F}_{i,{\sf r_{p}}(i)}>\\\ &>{\sf PS}(lt^{-})+{\sf
PS}(rt^{-})={\sf{M_{l}}}(i-1,j)-{\sf g}_{i-1,{\sf l_{p}}(i-1)}-{\sf
g}_{i-1,j}\geq\\\ &\geq{\sf PS}(lt^{\prime+}[i,...])+{\sf
PS}(rt_{1}^{+}[i,...]).\end{array}$
This contradiction proves our Property. ∎

######  Lemma 1.

Tables ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ can be found in
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}})$.

###### Proof.

Before calculation of ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ we need to find table
${\sf F}_{i,j}({\sf g})$ for each $i,j$. This table can be found in
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}})$. Also, we need in ${\sf
l_{p}}$ and ${\sf r_{p}}$, which can be found in ${\textit{O}}({\textit{H}})$.

It is enough to prove that every row of tables ${\sf{M_{l}}}$ and
${\sf{M_{r}}}$ can be found in ${\textit{O}}({\textit{W}})$. Let prove it by
induction on H.

Base case: Let find values for last row. For last row these tables contains
the sum of pair paths with length 1. Thus, any pair (with different begining)
don’t intersects between themselves.

$\begin{array}[]{lll}{\sf{M_{l}}}({\textit{H}}{-}1,j)={\sf
g}_{{\textit{H}}{-}1,{\sf l_{p}}({\textit{H}}{-}1)}+{\sf
g}_{{\textit{H}}{-}1,j}&$ for each $j=\max\\{{\sf
r_{p}}({\textit{H}}{-}1),{\sf
l_{p}}({\textit{H}}{-}1){+}1\\},..,{\textit{W}}{-}1.\\\
{\sf{M_{r}}}({\textit{H}}{-}1,j)={\sf g}_{{\textit{H}}{-}1,{\sf
r_{p}}({\textit{H}}{-}1)}+{\sf g}_{{\textit{H}}{-}1,j}&$ for each
$j=0,...,\min\\{{\sf l_{p}}({\textit{H}}{-}1),{\sf
r_{p}}({\textit{H}}{-}1)-1\\}.\end{array}$

This calculation requires ${\textit{O}}({\textit{W}})$ time.

Induction step: Suppose that known ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ for rows
$i,...,{{\textit{H}}{-}1}$, where $i>0$.

Then let find ${\sf{M_{l}}}$ for $(i-1)$-th row. By Note 10 it is enough to
find the ${\sf{M_{l}}}(i-1,j)$, for any $j\geq\max\\{{\sf l_{p}}(i{-}1)+1,{\sf
r_{p}}(i{-}1)\\}$.

Let $lP$ and $rP$ are ${\sf lrdtms}(i-1,{\sf l_{p}}(i-1),j)$ pair. Consider
all possible cases and find the sum ${\sf PS}(lP[i,...])+{\sf PS}(rP[i,...])$:

  1. 1.

For case $lP(i)<{\sf l_{p}}(i)$ and $rP(i)={\sf r_{p}}(i)$. Denote ${\sf
PS}(lP[i,...])+{\sf PS}(rP[i,...])$ for this case as $max_{1}(j)$. Then we get
$max_{1}(j)={\sf{M_{r}}}(i,lP(i))$ i.e.

$max_{1}(j)=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}$

where $b_{1}=\max\\{{\sf l_{p}}(i-1)-1,0\\}$ and $b_{2}=\min\\{{\sf
l_{p}}(i-1)+1,{\sf l_{p}}(i)-1,{\sf r_{p}}(i)-1\\}$

Due to rule (r1) we get ${\sf l_{p}}(i-1)+1\geq{\sf l_{p}}(i)$ and ${\sf
l_{p}}(i)-1\leq{\sf r_{p}}(i)-1$, then $b_{2}={\sf l_{p}}(i)-1$. Note that
$b_{1}\leq b_{2}$ iif $\max\\{{\sf l_{p}}(i{-}1),1\\}\leq{\sf l_{p}}(i)$.

Let find when restrictions of this case don’t contradict to (r1), (r3). It is
enough to check for possible positions of $lP(i)$ and $rP(i)$.

For $rP(i)$ we get $j{-}1\leq rP(i)\leq j{+}1$ and $rP(i)={\sf
r_{p}}(i)<{\textit{W}}$, then sufficient conditions for $rP(i)$ are
$j{-}1\leq{\sf r_{p}}(i)\leq j{+}1$. But by proposition $j\geq{\sf
r_{p}}(i-1)$ then by (r1) the condition $j\geq{\sf r_{p}}(i)-1$ is true
always.

Restrictions for $lP(i)$ are ${\sf l_{p}}(i-1)-1=lP(i-1)-1\leq lP(i)<{\sf
l_{p}}(i)$ and $0\leq lP(i)$.

Thus we get conditions when this case need to check

$j{-}1\leq{\sf r_{p}}(i),\max\\{{\sf l_{p}}(i{-}1),1\\}\leq{\sf l_{p}}(i).$
(1)

Thus, in common case, we can assume

$max_{1}(j)=\begin{cases}\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}&(\ref{cond1}),\\\
0&otherwise.\end{cases}$

  2. 2.

For case $lP(i)={\sf l_{p}}(i)$. Denote ${\sf PS}(lP[i,...])+{\sf
PS}(rP[i,...])$ for this case as $max_{2}(j)$. Then we get
$max_{2}(j)={\sf{M_{l}}}(i,rP(i))$ i.e.

$max_{2}(j)=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{l}}}(i,k)\\}$

where $b_{1}=\max\\{j-1,{\sf r_{p}}(i),{\sf l_{p}}(i)+1\\}$ and
$b_{2}=\min\\{j+1,{\textit{W}}-1\\}$

Note that $b_{1}\leq b_{2}$ iif $lpath(i)+2\leq{\textit{W}}$.

For $rP(i)$ we get restrictions $\max\\{{\sf l_{p}}(i)+1,{\sf r_{p}}(i)\\}\leq
rP(i)\leq{\textit{W}}-1$ and $j-1\leq rP(i)\leq j+1$. Since always ${\sf
r_{p}}(i)\leq\min\\{j+1,{\textit{W}}-1\\}$ and $j-1\leq{\textit{W}}-1$ then
required conditions for $rP(i)$ are $lpath(i)+1\leq j+1$ and ${\sf
l_{p}}(i)+2\leq{\textit{W}}$. But by proposition and (r1) we get $j\geq{\sf
l_{p}}(i-1)+1\geq{\sf l_{p}}(i)$ then we get that ${\sf l_{p}}(i)\leq j$ is
true always.

Restrictions for $lP(i)$ are $lP(i)={\sf l_{p}}(i)$ and $lP(i-1)={\sf
l_{p}}(i-1)$. Since ${\sf l_{p}}[i-1,i]$ satisfy to (r1) and (r3) then this
restriction always true for $lP[i-1,i]$.

Thus we get conditions for this case checking

${\sf l_{p}}(i)+2\leq{\textit{W}}.$ (2)

Thus, in common case, we can assume

$max_{2}(j)=\begin{cases}\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{l}}}(i,k)\\}&(\ref{cond2}),\\\
0&otherwise.\end{cases}$

  3. 3.

Consider case when $lP(i)<{\sf l_{p}}(i)$, $rP(i)>{\sf r_{p}}(i)$ and $j={\sf
r_{p}}(i-1)$.

Due to contradiction with Properties 5.1 and 5.2 this case impossible for
${\sf lrdtms}(i-1,{\sf l_{p}}(i-1),j)$ pair $lP$ and $rP$.

  4. 4.

Consider case when $lP(i)<{\sf l_{p}}(i)$, $rP(i)>{\sf r_{p}}(i)$ and $j>{\sf
r_{p}}(i-1)$. Denote ${\sf PS}(lP[i,...])+{\sf PS}(rP[i,...])$ for this case
as $max_{3}(j)$. Then by Property 8.4 we get

$max_{3}(j)=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}$

where $b_{1}=\max\\{0,{\sf l_{p}}(i-1)-1\\},b_{2}=\min\\{{\sf
l_{p}}(i-1)+1,{\sf l_{p}}(i)-1\\}={\sf l_{p}}(i)-1$ and
$b_{3}=\max\\{{\sf r_{p}}(i)+1,j-1\\},b_{4}=\min\\{j+1,{\textit{W}}-1\\}$.

Note that $b_{1}\leq b_{2}$ and $b_{3}\leq b_{4}$ iif $\max\\{1,{\sf
l_{p}}(i-1)\\}\leq{\sf l_{p}}(i),\ {\sf r_{p}}(i)+2\leq{\textit{W}}$.

This case possible only when ${\sf r_{p}}(i)<rP(i)\leq{\textit{W}}-1$,
$j{-}1\leq rP(i)\leq j{+}1$, ${\sf r_{p}}(i{-}1)<j$, ${\sf
l_{p}}(i{-}1){-}1\leq lP(i)<{\sf l_{p}}(i)$ and $0\leq lP(i)$. Then we get
condition of $max_{3}(j)$ existing

$\max\\{1,{\sf l_{p}}(i{-}1)\\}\leq{\sf l_{p}}(i),\ {\sf
r_{p}}(i){+}2\leq{\textit{W}},\ {\sf r_{p}}(i{-}1)<j.$ (3)

Thus, in common case, we can assume

$max_{3}(j)=\begin{cases}\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}&(\ref{cond3}),\\\
0&otherwise.\end{cases}$

Note that condition $b_{1}\leq b_{2}$ and $b_{3}\leq b_{4}$ follows from
$(\ref{cond3})$.

Thus exists $m\in\\{1,2,3\\}$ such that ${\sf PS}(lP[i,...])+{\sf
PS}(rP[i,...])=max_{m}(j)$. Then

${\sf PS}(lP[i,...])+{\sf
PS}(rP[i,...])\leq\max\\{max_{1}(j),max_{2}(j),max_{3}(j)\\}.$

Since ${\sf PS}(lP[i,...])+{\sf PS}(rP[i,...])\geq 0$ then ${\sf
PS}(lP[i,...])+{\sf PS}(rP[i,...])\geq max_{m}(j)$ when condition $(m)$ is
false for each $m\in\\{1,2,3\\}$. Since $max_{1}(j)$ and $max_{2}(j)$ is
result of reducing to an existing pairs of paths with maximum sum then ${\sf
PS}(lP[i,...])+{\sf PS}(rP[i,...])\geq max_{m}(j)$ for each $m\in\\{1,2\\}$.

Since $b_{1}\leq b_{2}$ and $b_{3}\leq b_{4}$ in case 4 follows from condition
$(\ref{cond3})$ then by Propety 9 we get that ${\sf PS}(lP[i,...])+{\sf
PS}(rP[i,...])\geq max_{3}(j)$. Thus using ${\sf{M_{l}}}(i-1,j)={\sf
PS}(lP[i,...])+{\sf PS}(rP[i,...])+{\sf g}_{i-1,{\sf l_{p}}(i-1)}+{\sf
g}_{i-1,j}$ we get

${\sf{M_{l}}}(i-1,j)={\sf g}_{i-1,{\sf l_{p}}(i-1)}+{\sf
g}_{i-1,j}+\max\\{max_{1}(j),max_{2}(j),max_{3}(j)\\}.$

Thus in ${\textit{O}}(1)$ we can find ${\sf{M_{l}}}(i-1,j)$ for any
$j\in\\{\max\\{{\sf l_{p}}(i{-}1)+1,{\sf
r_{p}}(i{-}1)\\},...,{\textit{W}}-1\\}$. Then in ${\textit{O}}({\textit{W}})$
we can find ${\sf{M_{l}}}$ for row $i-1$. Similarly in
${\textit{O}}({\textit{W}})$ we can find ${\sf{M_{r}}}$ for row $i-1$. ∎

More exactly, this algorithm spent
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}})$ of comparisons and sums of
numbers like ${\sf F}_{i,j}$, ${\sf{M_{l}}}(i,j)$, ${\sf l_{p}}(i)$. Since
values of ${\sf g}$ bounded by value $C$, then these numbers have length
${\textit{O}}(\log({\textit{H}}\cdot C))$.

If $C=f(H)$ is less than any polynomial function of H, then these values have
length $o(\log({\textit{H}}))$ i.e. less than length of addresses to elements
of input data, therefore we ignore linear operations with these values.

If $f$ is not less than some polynomial function of H, then complexity is
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}})$ of linear operations with
integers of length ${\textit{O}}(\log(f({\textit{H}})))$. Thus, we have full
complexity
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}}{\cdot}\log(f({\textit{H}})))$.
But by our assumption, the length of input data is
$\Theta({\textit{H}}{\cdot}{\textit{W}}{\cdot}\log(f({\textit{H}})))$. Thus,
we got pure linear algorithm.

####  3.1.1 Simplification of ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ search

Here we use designations from induction step of Lemma 1.

Assume that $lP(i)<{\sf l_{p}}(i)$. Note that pair $b_{1},b_{2}$ of case 1 are
same as pair $b_{1},b_{2}$ of case 4. Also using restriction $rP(i)={\sf
r_{p}}(i)$ in case 1 we get

$\max_{k={\sf r_{p}}(i),...,b_{4}}\\{{\sf F}_{i,k}\\}={\sf F}_{i,{\sf
r_{p}}(i)}$

for any ${\sf r_{p}}(i)\leq b_{4}\leq\min\\{j+1,{\textit{W}}-1\\}$. Thus we
can assume that $b_{4}$ from case 4 and

$max_{1}(j)=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k={\sf
r_{p}}(i),...,b_{4}}\\{{\sf F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}.$

Also we can extend restriction for case 4 by addition of restriction of cases
1 and 3. Let $b_{3}^{\prime}=\max\\{{\sf r_{p}}(i),j-1\\}$. Then in case
$rP(i)={\sf r_{p}}(i)$ we get ${\sf r_{p}}(i)=rP(i)\geq j-1$ then we get
$b_{3}^{\prime}={\sf r_{p}}(i)$ then

$max_{1}(j)=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3}^{\prime},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}.$

If $rP(i)>{\sf r_{p}}(i)$ then by case 3 we get that case $j={\sf r_{p}}(i-1)$
impossible. Then $j>{\sf r_{p}}(i-1)$ and we get restrictions of case 4 and
conditions of Property 8.

In case when $j{-}1>{\sf r_{p}}(i)$ we get $b_{3}^{\prime}=b_{3}$.

Consider case when $j{-}1\leq{\sf r_{p}}(i)$ i.e. $b_{3}^{\prime}={\sf
r_{p}}(i)=b_{3}-1$. Then by Property 8 exists $ri>i$ such that
$rP[i-1,...,ri]$ is subpath of some ${\sf RP}$ path defined by ${\sf F}$ then

$rP(i)\in\operatorname*{arg\,max}_{k=b_{3}^{\prime},...,b_{4}}\\{{\sf
F}_{i,k}\\}.$

Since $b_{3}^{\prime}={\sf r_{p}}(i)<rP(i)$ and $b_{3}^{\prime}+1=b_{3}$ then
$rP(i)\in\\{b_{3},...,b_{4}\\}$ then

$\max_{k=b_{3},...,b_{4}}\\{{\sf
F}_{i,k}\\}=\max_{k=b_{3}^{\prime},...,b_{4}}\\{{\sf F}_{i,k}\\}$

Thus if $rP(i)>{\sf r_{p}}(i)$ we get

$max_{3}(j)=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3}^{\prime},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}.$

Thus, in common case, we can combine cases 1, 3 and 4 with one restriction
$lP(i)<{\sf l_{p}}(i)$ and common maximum formula

$max_{1}^{\prime}(j)=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3}^{\prime},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}.$

Let find conditions of $max_{1}^{\prime}$ existing.

For $rP(i)$ we get ${\sf r_{p}}(i)\leq rP(i)\leq{\textit{W}}{-}1$ and
$j{-}1\leq rP(i)\leq j{+}1$ then we get ${\sf r_{p}}(i)\leq j+1$. But
$j=rP(i-1)\geq rP(i)-1\geq{\sf r_{p}}(i)+1$ allways.

For $lP(i)$ we get ${\sf l_{p}}(i{-}1){-}1\leq lP(i)<{\sf l_{p}}(i)$ and
$0\leq lP(i)$. Then we get conditions of $max_{1}^{\prime}(j)$ existing

$\max\\{1,{\sf l_{p}}(i{-}1)\\}\leq{\sf l_{p}}(i).$ (4)

Thus in common case we can assume

$max_{1}^{\prime}(j)=\begin{cases}\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3}^{\prime},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}&(\ref{cond4})\\\
0&otherwise.\end{cases}$

Then

${\sf{M_{l}}}(i-1,j)={\sf g}_{i-1,{\sf l_{p}}(i-1)}+{\sf
g}_{i-1,j}+\max\\{max_{1}^{\prime}(j),max_{2}(j)\\}$

Implementation of this version search of ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$
represented at listing 3 in function get_M using programing language Python.

###  3.2 Reducing problem to lrdtms(0,0,W-1) pair

######  Definition 14.

Denote subset of common cells between paths $t_{1}$ and $t_{2}$ as $t_{1}\cap
t_{2}$.
Set of all cells of paths $t_{1}$ and $t_{2}$ as $t_{1}\cup t_{2}$.
Set of all cells of path $t_{1}$ without cells of path $t_{2}$ as
$t_{1}\setminus t_{2}$.

######  Definition 15.

Consider paths $lt$ and $rt$. Let rows $i_{1}$ and $i_{2}$ such that
$lt(i)=rt(i)$ for each $i=i_{1}+1,...,i_{2}-1$ and either
$lt(i_{1})<rt(i_{1}),\ lt(i_{2})>rt(i_{2})$ or $lt(i_{1})>rt(i_{1}),\
lt(i_{2})<rt(i_{2})$. Then call pair $i_{1},i_{2}$ as cross over pair.

######  Property 10.

For any paths $lt$ and $rt$, with begining from cells $(0,0)$ and
$(0,{\textit{W}}-1)$, exists paths $lt^{\prime}$ and $rt^{\prime}$ with
begining from $(0,0)$ and $(0,{\textit{W}}-1)$ respectively, with $lt\cup
rt=lt^{\prime}\cup rt^{\prime}$ (as corrolary with same common sum i.e. ${\sf
PS}(lt\cup rt)={\sf PS}(lt^{\prime}\cup rt^{\prime})$), and inequality
$lt^{\prime}(i)\leq rt^{\prime}(i)$ for each $i$.

###### Proof.

WLOG suppose that $lt$ and $rt$ have minimum cross over pairs from all paths
$lt^{\prime}$ and $rt^{\prime}$ starts from $(0,0)$ and $(0,{\textit{W}}-1)$
respectively with same common sum (equal to $N$), and $lt\cup
rt=lt^{\prime}\cup rt^{\prime}$. And suppose that between $lt$ and $rt$ exists
cross over pair.

Then, using Property 1, we can reduce number of cross over pairs by swaping
tails of $lt$ and $rt$. Since swaping don’t changes the set of cells of paths
then we get $lt\cup rt=lt^{\prime}\cup rt^{\prime}$. Thus we get contradiction
with minimum cross over pairs between $lt$ and $rt$.

Thus we get $lt(i)\leq rt(i)$ for each $i$. ∎

######  Property 11.

Suppose that our grid $g$ without negative values. Consider paths $lt$ and
$rt$ with begining from $(0,0)$ and $(0,{\textit{W}}-1)$, and $lt(i)\leq
rt(i)$ for each $i$.

Then exists paths $lt^{\prime}$ and $rt^{\prime}$ with begining from $(0,0)$
and $(0,{\textit{W}}-1)$ respectively, such that
$lt^{\prime}(i)<rt^{\prime}(i)$ for each $i$ (i.e. $lt^{\prime}$ don’t
intersects with $rt^{\prime}$), and ${\sf PS}(lt^{\prime})+{\sf
PS}(rt^{\prime})\geq{\sf PS}(lt)+{\sf PS}(rt)-{\sf PS}(lt\cap rt)$.

###### Proof.

Denote ${\sf PS}(lt)+{\sf PS}(rt)-{\sf PS}(lt\cap rt)$ as $N$. WLOG assume
that $lt$ and $rt$ have minimum common cells among all paths starts from
$(0,0)$ and $(0,W-1)$ cells, and with common sum equal to $N$ or grater (i.e.
${\sf PS}(lt)+{\sf PS}(rt)-{\sf PS}(lt\cap rt)\geq N$).

And suppose that row $i_{1}$ such that $lt(i_{1})=rt(i_{1})$ and $lt(i)<rt(i)$
for each $i<i_{1}$. Denote $lt(i_{1})$ as $j_{1}$.

Consider case when $lt(i_{1}-1)<j_{1}$.

Due to rule of moving (r1), after $k$ steps from cell $(i_{1},j_{1})$ left and
rigth robots will be located on cells $(i_{1}+k,j^{\prime})$ and
$(i_{1}+k,j^{\prime\prime})$ respectively, for some
$j^{\prime},j^{\prime\prime}\leq j_{1}+k$. I.e. $lt(i_{1}+k)\leq
rt(i_{1}+k)\leq j_{1}+k$.

Consider cases:

  * •

Suppose that not all moves of left robot are rigthmost after row $i_{1}$. I.e.
exists $i^{\prime}>i_{1}$ such that ${(lt(i)-j_{1})\geq(i{-}i_{1})}$ for each
$i=i_{1},...,i^{\prime}{-}1$ and
$(lt(i^{\prime})-j_{1})<(i^{\prime}{-}i_{1})$,

Then $j_{1}+i-i_{1}\leq lt(i_{1}+i-i_{1})\leq rt(i_{1}+i-i_{1})\leq
j_{1}+i-i_{1}$ for each $i=i_{1},...,i^{\prime}{-}1$. I.e.
$lt[i_{1},...,i^{\prime}-1]=rt[i_{1},...,i^{\prime}-1]$.

Consider concatenation $lmp^{\prime}$ such that:
$\begin{array}[]{lll}lmp^{\prime}[...,i_{1}-1]&=lt[...,i_{1}-1],\\\
lmp^{\prime}(i_{1}+k)&=j_{1}-1+k,\ k=0,...,i^{\prime}-1-i_{1},\\\
lmp^{\prime}[i^{\prime},...]&=lt[i^{\prime},...].\end{array}$

Then $lmp^{\prime}[...,i_{1}-1]$ and $lmp^{\prime}[i^{\prime},...]$ are
subpaths. Also, $lmp^{\prime}[i_{1},...,i^{\prime}-1]$ is subpath with
rigthmost moves.

Let prove that moves from $lmp^{\prime}(i_{1}-1)$ to $lmp^{\prime}(i_{1})$ and
from $lmp^{\prime}(i^{\prime}-1)$ to $lmp^{\prime}(i^{\prime})$ are
corresponds to move rules.

Using rules of move for $lt$ we get $lmp^{\prime}(i_{1}-1)=lt(i_{1}-1)\geq
lt(i_{1})-1=lmp^{\prime}(i_{1})$. The other side
$lmp^{\prime}(i_{1})=lt(i_{1})-1>lt(i_{1}-1)-1=lmp^{\prime}(i_{1}-1)-1$. I.e.
$lmp^{\prime}(i_{1})=lmp^{\prime}(i_{1}-1)$. Thus move from
$lmp^{\prime}(i_{1}-1)$ to $lmp^{\prime}(i_{1})$ is correct (i.e. corresponds
to moving rules).

By assumption $lmp(i^{\prime})-j_{1}<(i^{\prime}-i_{1})$ we get
$j_{1}>lt(i^{\prime})-(i^{\prime}-i_{1})$. Then for $k=i^{\prime}-1-i_{1}$ we
get
$lmp^{\prime}(i^{\prime}-1)=lmp^{\prime}(i_{1}+k)=j_{1}-1+k>lt(i^{\prime})-2=lmp^{\prime}(i^{\prime})-2$.
I.e. $lmp^{\prime}(i^{\prime}-1)\geq lmp^{\prime}(i^{\prime})-1$.

By assumption $lt(i^{\prime}-1)-j_{1}\geq(i^{\prime}-1-i_{1})$ we get
$j_{1}\leq lt(i^{\prime}-1)-(i^{\prime}-1-i_{1})$. Then for
$k=i^{\prime}-1-i_{1}$ we get $lmp^{\prime}(i^{\prime}-1)=j_{1}+k-1\leq
lt(i^{\prime}-1)-1\leq lt(i^{\prime})$.

I.e. we get $lmp^{\prime}(i^{\prime}-1)\leq lmp^{\prime}(i^{\prime})\leq
lmp^{\prime}(i^{\prime}-1)+1$. Then move from $lmp^{\prime}(i^{\prime}-1)$ to
$lmp^{\prime}(i^{\prime})$ is correct too. Thus $lmp^{\prime}$ is path.

By definition $lmp^{\prime}(i)=j_{1}-1+(i-i_{1})$ for each
$i=i_{1},...,i^{\prime}-1$. Then, using assumption $lt(i)-j_{1}\geq(i-i_{1})$
for each $i=i_{1},...,i^{\prime}-1$, we get
$(lt(i)-j_{1}+(j_{1}-1+(i-i_{1})))\geq(i-i_{1})+lmp^{\prime}(i)$ for each
$i=i_{1},...,i^{\prime}-1$. I.e. $lt(i)\neq
lmp^{\prime}(i),i=i_{1},...,i^{\prime}-1$.

Denote ${\sf PS}(lmp_{1}\cap rmp_{1})$ and ${\sf PS}(lmp^{\prime}\cap rt)$ as
$d$ and $d^{\prime}$ respectively.

Since $lmp^{\prime}(i)\neq lt(i)=rt(i)$ for each $i=i_{1},...,i^{\prime}{-}1$,
then $d^{\prime}=d-{\sf PS}(lt[i_{1},...,i^{\prime}{-}1])$. Since $g$ consists
of nonnegative values, then ${\sf
PS}(lmp^{\prime}[i_{1},...,i^{\prime}-1])\geq 0$. Then
$\begin{array}[]{ll}N&={\sf PS}(lt)+{\sf PS}(rt)-d=\\\ &={\sf
PS}(lt[...,i_{1}{-}1])+{\sf PS}(lt[i_{1},...,i^{\prime}{-}1])+{\sf
PS}(lt[i^{\prime},...])+{\sf PS}(rt)-d=\\\ &={\sf PS}(lt[...,i_{1}{-}1])+{\sf
PS}(lt[i^{\prime},...])+{\sf PS}(rmp)-d^{\prime}\leq\\\ &\leq{\sf
PS}(lt[...,i_{1}{-}1])+{\sf PS}(lmp^{\prime}[i_{1},...,i^{\prime}{-}1])+{\sf
PS}(lt[i^{\prime},...])+{\sf PS}(rt)-d^{\prime}=\\\ &={\sf
PS}(lmp^{\prime})+{\sf PS}(rt)-{\sf PS}(lmp^{\prime}\cap rt).\end{array}$

Thus we get paths $lmp^{\prime}$ and $rt$ from $(0,0)$ and $(0,W{-}1)$
respectively with common sum not less than common sum of $lt$ and $rt$. Since
$rt$ has common cells with $lmp^{\prime}$ less than with $lt$, then we get
contradiction with minimum of common cells between $lt$ and $rt$.

  * •

${(lt(i)-j_{1})\geq(i{-}i_{1})}$ for each $i\geq i_{1}$.

Then $j_{1}+i-i_{1}\leq lt(i)\leq rt(i_{1}+(i-i_{1}))\leq j_{1}+(i-i_{1})$ for
each $i\geq i_{1}$. I.e. $lt[i_{1},...]=rt[i_{1},...]$ and
$lt(i)=j_{1}+i-i_{1}$ for each $i\geq i_{1}$.

Consider concatenation $lmp^{\prime}$ such that:
$\begin{array}[]{lll}lmp^{\prime}[...,i_{1}-1]&=lt[...,i_{1}-1],\\\
lmp^{\prime}(i)&=lt(i_{1}-1)$ for each $i\geq i_{1}.\end{array}$

Then $lmp^{\prime}[...,i_{1}{-}1]$ and $lmp^{\prime}[i_{1},...]$ are paths.
Also, $lmp^{\prime}(i_{1})=lt(i_{1}{-}1)=lmp^{\prime}(i_{1}{-}1)$ i.e. move
from $lmp^{\prime}(i_{1}{-}1)$ to $=lmp^{\prime}(i_{1})$ is correct. Thus
$lmp^{\prime}$ is path.

Also, $lmp^{\prime}(i)=lt(i_{1}-1)<j_{1}\leq j_{1}+i-i_{1}=lt(i)$ for each
$i\geq i_{1}$.

Denote ${\sf PS}(lt\cap rt)$ and ${\sf PS}(lmp^{\prime}\cap rt)$ as $d$ and
$d^{\prime}$ respectively.

Since $lmp^{\prime}(i)<lt(i)=rt(i)$ for each $i\geq i_{1}$, then
$d^{\prime}=d-{\sf PS}(lt[i_{1},...])$. Since $g$ consists of nonnegative
values, then ${\sf PS}(lmp^{\prime}[i_{1},...,i^{\prime}-1])\geq 0$. Then
$\begin{array}[]{ll}N&={\sf PS}(lt)+{\sf PS}(rt)-d={\sf
PS}(lt[...,i_{1}{-}1])+{\sf PS}(lt[i_{1},...])+{\sf PS}(rt)-d=\\\ &={\sf
PS}(lt[...,i_{1}{-}1])+{\sf PS}(rt)-d^{\prime}\leq\\\ &\leq{\sf
PS}(lt[...,i_{1}{-}1])+{\sf PS}(lmp^{\prime}[i_{1},...])+{\sf
PS}(rt)-d^{\prime}=\\\ &={\sf PS}(lmp^{\prime})+{\sf PS}(rt)-{\sf
PS}(lmp^{\prime}\cap rt).\end{array}$

Thus, like in previous case, we get contradiction with minimum of common cells
between $lt$ and $rt$.

It remains to consider case when $lt(i_{1}-1)\geq j_{1}$. Then
$rt(i_{1}-1)>lt(i_{1}-1)\geq j_{1}=rt(i_{1})$, and, due to simmetry, this case
lead us to contradiction like in previous case. ∎

######  Property 12.

Consider paths $lt$ and $rt$ with begining from $(0,0)$ and
$(0,{\textit{W}}-1)$ respectively, and $lt(i)<rt(i)$ for each $i$. Then exists
${\sf LP}(0,0)$ and ${\sf RP}(0,{\textit{W}}-1)$ paths $lt^{\prime}$ and
$rt^{\prime}$ respectively such that $lt^{\prime}(i)<rt^{\prime}(i)$ for each
$i$, and ${\sf PS}(lt^{\prime})+{\sf PS}(rt^{\prime})\geq{\sf PS}(lt)+{\sf
PS}(rt)$.

###### Proof.

Denote ${\sf PS}(lt)+{\sf PS}(rt)$ as $N$. WLOG we can assume that $lt(i)$ has
minimum amount of rows $i$ such that $lt(i)>{\sf l_{p}}(i)$ among all paths
$lt^{\prime}$ with begining on $(0,0)$ without intersections with $rt$, and
with sum ${\sf PS}(lt^{\prime})+{\sf PS}(rt)\geq N$.

Suppose that $lt(i)$ isn’t ${\sf LP}_{0,0}$ path. Then exists row $i_{1}$ such
that $lt(i)\leq{\sf l_{p}}(i)$ for each $i<i_{1}$ and $lt(i_{1})>{\sf
l_{p}}(i_{1})$ (i.e. $i_{1}>0$). Then consider cases:

  * •

If exists $i_{2}>i$ such that $lt(i)>{\sf l_{p}}(i)$ for each
$i=i_{1},...,i_{2}-1$ and $lt(i_{2})\leq{\sf l_{p}}(i_{2})$.

Then consider concatenation $t_{1}$: $t_{1}[...,i_{1}-1]=lt[...,i_{1}-1]$,
$t_{1}[i_{1},...]={\sf l_{p}}[i_{1},...]$.

And concatenation $lmp^{\prime}$:
$lmp^{\prime}[...,i_{2}-1]=t_{1}[...,i_{2}-1]$,
$lmp^{\prime}[i_{2},...]=lt[i_{2},...]$.

Due to Property 1 the $t_{1}$ is path. Then due to Property 1 the
$lmp^{\prime}$ is path too.

Thus we get path $lmp^{\prime}$:
$\begin{array}[]{ll}lmp^{\prime}[...,i_{1}-1]&=lt[...,i_{1}-1],\\\
lmp^{\prime}[i_{1},...,2_{1}-1]&={\sf l_{p}}[i_{1},...,i_{2}-1],\\\
lmp^{\prime}[i_{2},...]&=lt[i_{2},...].\end{array}$

Sumilarly we can prove that concatenation $t_{2}$:
$\begin{array}[]{ll}t_{2}[...,i_{1}-1]&={\sf l_{p}}[...,i_{1}-1],\\\
t_{2}[i_{1},...,2_{1}-1]&=lt[i_{1},...,i_{2}-1],\\\ t_{2}[i_{2},...]&={\sf
l_{p}}[i_{2},...].\end{array}$
is path too.

Due to ${\sf l_{p}}$ defined by ${\sf F}_{0,0}$ and $t_{2}$ is path with
begining on $(0,0)$
$\begin{array}[]{ll}{\sf PS}(lt[i_{1},...,i_{2}{-}1])&={\sf PS}(t_{2})-{\sf
PS}({\sf l_{p}}[...,i_{1}{-}1])-{\sf PS}({\sf l_{p}}[i_{2},...])\leq\\\
&\leq{\sf PS}({\sf l_{p}})-{\sf PS}({\sf l_{p}}[...,i_{1}{-}1])-{\sf PS}({\sf
l_{p}}[i_{2},...])=\\\ &={\sf PS}({\sf
l_{p}}[i_{1},...,i_{2}{-}1]).\end{array}$

Then
$\begin{array}[]{ll}{\sf PS}(lmp^{\prime})&={\sf PS}(lt[...,i_{1}-1])+{\sf
PS}({\sf l_{p}}[i_{1},...,i_{2}-1])+{\sf PS}(lt[i_{2},...])\geq\\\ &\geq{\sf
PS}(lt[...,i_{1}-1])+{\sf PS}(lt[i_{1},...,i_{2}-1])+{\sf
PS}(lt[i_{2},...])={\sf PS}(lt).\end{array}$

Since ${\sf l_{p}}(i)\leq lt(i)$ for each $i=i_{1},...,i_{2}-1$, then
$lmp^{\prime}(i)\leq lt(i)<rt(i)$ for each $i$.

Thus we get path $lmp^{\prime}$ without intersections with $rt$ and ${\sf
PS}(lmp^{\prime})+{\sf PS}(rt)\geq{\sf PS}(lt)+{\sf PS}(rt)=N$.

But $lmp^{\prime}$ has less rows $i$ such that $lmp^{\prime}(i)>{\sf
l_{p}}(i)$ which contradicts to minimum of these rows in $lt$. Thus $lt$ is
${\sf LP}_{0,0,}$ path.

  * •

$lt(i)>lpath(i)$ for each $i\geq i_{1}$.

Then consider concatenations $lmp^{\prime}$ and $t_{2}$:
$\begin{array}[]{llll}lmp^{\prime}[...,i_{1}-1]&=lt[...,i_{1}-1],&lmp^{\prime}[i_{1},...]&={\sf
l_{p}}[i_{1},...],\\\
t_{2}[...,1_{1}-1]&=lpath[...,i_{1}-1],&t_{2}[i_{1},...]&=lt[i_{1},...].\end{array}$

Due to Property 1 the $lmp^{\prime}$ and $t_{2}$ are paths.

Due to ${\sf l_{p}}$ defined by ${\sf F}_{0,0}$ and $t_{2}$ is path with
begining on $(0,0)$
$\begin{array}[]{ll}{\sf PS}(lt[i_{1},...])&={\sf PS}(t_{2})-{\sf PS}({\sf
l_{p}}[...,i_{1}{-}1])\leq\\\ &\leq{\sf PS}({\sf l_{p}})-{\sf PS}({\sf
l_{p}}[...,i_{1}{-}1])={\sf PS}({\sf l_{p}}[i_{1},...]).\end{array}$

Then
$\begin{array}[]{ll}{\sf PS}(lmp^{\prime})&={\sf PS}(lt[...,i_{1}-1])+{\sf
PS}({\sf l_{p}}[i_{1},...])\geq\\\ &\geq{\sf PS}(lt[...,i_{1}-1])+{\sf
PS}(lt[i_{1},...])={\sf PS}(lt).\end{array}$

Since ${\sf l_{p}}(i)\leq lt(i)$ for each $i\geq i_{1}$, then
$lmp^{\prime}(i)\leq lt(i)<rt(i)$ for each $i$.

Thus we get path $lmp^{\prime}$ without intersections with $rt$ and ${\sf
PS}(lmp^{\prime})+{\sf PS}(rt)\geq{\sf PS}(lt)+{\sf PS}(rt)=N$.

But $lmp^{\prime}$ has less rows $i$ such that $lmp^{\prime}(i)>{\sf
l_{p}}(i)$ which contradicts to minimum of these rows in $lt$. Thus $lt$ is
${\sf LP}_{0,0,}$ path.

Similarly we can prove that $rt$ is ${\sf RP}_{0,W-1}$ path. ∎

######  Definition 16.

Consider pair of paths $l$ and $r$, with intersection in $i$-th row. Assume
that there are no paths $l^{\prime}$ and $r^{\prime}$ such that they contains
all cells of $l$ and $r$, but without intersections at $i$-th row (i.e.
$(l\cup r)\varsubsetneq(l^{\prime}\cup r^{\prime})$), and all cells
$(l^{\prime}\cup r^{\prime})\setminus(l\cup r)$ with nonnegative values. Then
call paths $l$ and $r$ as $(i,l(i))$–linked pair. And call cell $(i,j)$ as
bottleneck if there are $(i,j)$–linked pair.

######  Lemma 2.

Let $N$ is maximum number of cherries which can be collected by 2 robots with
begining on $(0,0)$ and $(0,{\textit{W}}{-}1)$ cells. If is true at least one
of next conditions:

  1. 1.

All values of grid ${\sf g}$ is nonnegative.

  2. 2.

The ${\sf g}$ don’t has bottlenecks.

then any ${\sf lrdtms}(0,0,{\textit{W}}{-}1)$ pair $lt$ and $rt$ have ${\sf
PS}(lt)+{\sf PS}(rt)=N$.

###### Proof.

Let paths $lmp$ and $rmp$ starts from $(0,0)$ and $(0,{\textit{W}}-1)$ cells
respectively and pickups maximum cherries. I.e. ${\sf PS}(lmp)+{\sf
PS}(rmp)-{\sf PS}(lmp\cap rmp)=N$.

By Property 10 we can assume that $lmp(i)\leq rmp(i)$ for each $i$.

  1. 1.

Suppose that all values of ${\sf g}$ is nonnegative.

Then by Property 11 we can assume that $lmp(i)<rmp(i)$ for each $i$.

  2. 2.

Suppose that ${\sf g}$ don’t has bottlenecks.

WLOG assume that $lt$ and $rt$ have minimum of intersections among all pairs
of paths with begining from $(0,0)$ and $(0,{\textit{W}}-1)$, and common sum
equal to $N$ or grater.

Suppose that $lt$ intersects with $rt$.

Since grid ${\sf g}$ don’t has bottlenecks, then exists paths $lt^{\prime}$
and $rt^{\prime}$ such that $(lt\cup rt)\varsubsetneq(lt^{\prime}\cup
rt^{\prime})$, and cells $(lt^{\prime}\cup rt^{\prime})\setminus(lt\cup rt)$
without negative values.

By Property 10 exists $lt^{\prime\prime}$ and $rt^{\prime\prime}$ started from
$(0,0)$ and $(0,{\textit{W}}-1)$ without cross over pairs, and
$(lt^{\prime}\cup rt^{\prime})=(lt^{\prime\prime}\cup rt^{\prime\prime})$.

Thus we get paths $lt^{\prime\prime}$ and $rt^{\prime\prime}$ started from
$(0,0)$ and $(0,{\textit{W}}-1)$ such that $lt^{\prime\prime}(i)\leq
rt^{\prime\prime}(i)$ for each $i$, and with common sum
${\sf PS}(lt^{\prime\prime}\cup rt^{\prime\prime})={\sf PS}(lt^{\prime}\cup
rt^{\prime})={\sf PS}(lt\cup rt)+{\sf PS}((lt^{\prime}\cup
rt^{\prime})\setminus(lt\cup rt))\geq{\sf PS}(lt\cup rt)=N$.

But $lt^{\prime\prime}$ and $rt^{\prime\prime}$ have less intersections than
$lt$ and $rt$, that contradicts with our assumption.

Thus $lt$ don’t intersects with $rt$. Then $lt(i)<rt(i)$ for each $i$. Then,
as in previous case, we can assume that $lmp(i)<rmp(i)$ for each $i$.

Then by Property 12 exists ${\sf LP}_{0,0}$ and ${\sf RP}_{0,W{-}1}$ paths
$lmp^{\prime}$ and $rmp^{\prime}$ respectively without intersections, and
${\sf PS}(lmp^{\prime})+{\sf PS}(rmp^{\prime})=N$. Since $N$ is upper bound
for collected cherries by any pair of ${\sf LP}_{0,0}$ and ${\sf
RP}_{0,{\textit{W}}{-}1}$ paths then $lmp^{\prime}$ and $rmp^{\prime}$ are
${\sf lrdtms}(0,0,{\textit{W}}-1)$ pair.

Due to uniqueness of maximum, all ${\sf lrdtms}(0,0,{\textit{W}}{-}1)$ pairs
have same sum i.e. $N$. ∎

##  4 Linear solution

######  Theorem 1.

The “Cherry Pickup II” problem has a linear solution.

###### Proof.

Since count of cherries in cells are nonnegative values, then all values of
${\sf g}$ are nonnegative. According to Lemma 2.1 and start positions of
robots it is enough to find the sum of any ${\sf lrdtms}(0,0,{\textit{W}}-1)$
pair in grid with nonnegative values. According to definitions of
${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ this sum is equal to
${\sf{M_{l}}}(0,{\textit{W}}-1)$ and ${\sf{M_{r}}}(0,0)$. According to Lemma 1
we can find the tables ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ in
${\textit{O}}({\textit{H}}\cdot{\textit{W}})$. ∎

Algorithm implementation in Python showed in listings below. Finding ${\sf F}$
showed in listing 1, for ${\sf l_{p}}$ and ${\sf r_{p}}$ in listing 2, for
${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ in listing 3. Main function with solution in
listing 4.

######  Theorem 2.

If there are negative values in ${\sf g}$, but there are no bottlenecks, then
problem can be solved by finding maximum sum of two node-disjoint paths on
${\sf g}$.

###### Proof.

Since ${\sf g}$ don’t has bootlenecks, then according to Lemma 2.2 and start
positions of robots it is enough to find the sum of any ${\sf
lrdtms}(0,0,{\textit{W}}-1)$ pair. According to definitions of ${\sf{M_{l}}}$
and ${\sf{M_{r}}}$ this sum is equal to ${\sf{M_{l}}}(0,{\textit{W}}-1)$ and
${\sf{M_{r}}}(0,0)$. According to Lemma 1 we can find the tables
${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ in
${\textit{O}}({\textit{H}}\cdot{\textit{W}})$. ∎

###  4.1 Reducing of DM to finding maximum sum of two node-DP

Problem description:

Given a grid ${\sf g}_{DM}$ of size $N{\times}N$ with values in cells $0,1$
and $-1$:

$0$ means there is no diamond, but you can go through this cell;

$1$ means the diamond (i.e. you can go through this cell and pick up the
diamond);

$-1$ means that you can’t go through this cell.

We start at cell $(0,0)$ and reach the last cell $(N{-}1,N{-}1)$, and then
return back to $(0,0)$ collecting maximum number of diamonds:

Going to last cell we can move only right and down;

Going back we can move only left and up.

Solution:

Let ${\sf g}_{1}$, ${\sf g}_{2}$ and ${\sf g}_{3}$ are grids of size
$(2N{-}1){\times}(2N{-}1)$. And ${\sf g}_{4}$ is grid of size
$(3N{-}2){\times}(2N{-}1)$. Denote $N-1$ as $n$. Then DM can be reduced to our
LS of CP2 (without proof of correctnes):

  1. 1.

Check matrix for reachability by 1 robot. If not richable then return 0.

  2. 2.

Turn matrix clockwise by $45^{\circ}$. I.e. for each $i=0,...,n,j=0,...,n$

${\sf g}_{1}[i+j][n+i-j]={\sf g}_{DM}[i][j].$

  3. 3.

Add cells between horizontally neighboring cells. Also add under upper cells,
except $(0,n)$, by one cell. Fill cell by $-10N$ if bottom neighbor is $-1$,
or both horizontally neighboring cells are $-1$. Otherwise, fill by $0$. I.e.
for each $i=0,...,n,j=0,...,n$ where $i+j\geq 1$

${\sf g}_{1}[i{+}j{-}1][n{+}i{-}j]=\begin{cases}-10N&{\sf
g}_{1}[i{+}j][n{+}i{-}j]=-1,\\\ -10N&{\sf g}_{1}[i{+}j{-}1][n{+}i{-}j{-}1]=-1\
and\ {\sf g}_{1}[i{+}j{-}1][n{+}i{-}j{+}1]=-1,\\\ 0&otherwise.\end{cases}$

  4. 4.

Add corners, and fill them by $-10N$, except top and bottom rows. Fill
unvalued cells by $0$. I.e. for each $i=0,...,2n,j=0,...,2n$

${\sf g}_{2}[i][j]=\begin{cases}-10N&0<i<2n\ and\ (i{+}j<n\ or\ i{+}j>3n\ or\
i{+}n<j\ or\ i>j{+}n),\\\ 0&i=0\ and\ (j<n-1\ or\ j>n+1),\\\ 0&i=2n\ and\
j\neq n,\\\ {\sf g}_{1}[i][j]&otherwise.\end{cases}$

  5. 5.

Change values $-1$ by $-10N$. I.e. for each $i=0,...,2n,j=0,...,2n$

${\sf g}_{3}[i][j]=\begin{cases}-10N&g_{2}[i][j]=-1,\\\ {\sf
g}_{2}[i][j]&otherwise.\end{cases}$

  6. 6.

Add on top the matrix of size $n{\times}(2n+1)$ filled by $0$. I.e. for each
$i=0,...,3n,j=0,...,2n$

${\sf g}_{4}[i][j]=\begin{cases}0&i<n,\\\ {\sf g}_{3}[i-n][j]&i\geq
n.\end{cases}$

  7. 7.

Apply our LS of CP2 for grid ${\sf g}_{4}$ and return answer.

Since our algorithm looking for paths without intersections, therefore by
instruction 3 we make double ”road” with zero-sum for every reachable path to
avoid bottlenecks. Therefore, after instruction 6, due to Theorem 2, we can
get answer by applying our LS to ${\sf g}_{4}$.

First instruction can be checked by linear time using BFS. Instructions 2 – 6
are linear transformations. And last instruction has linear comlexity.

More exatly this reducing used linear operations with values at most
${\textit{O}}(N^{2})$. I.e. these values have lengths ${\textit{O}}(\log(N))$
same as lengths of addresses to rows. Therefore, we ignore these operations
for complexity estimation.

###  4.2 Some optimisation

######  Definition 17.

Let $(fi,fj)$ is cell of first (least by rows) intersection of ${\sf l_{p}}$
with ${\sf r_{p}}$.

######  Definition 18.

Let lPmax and rPmax are ${\sf lrdtms}(0,0,{\textit{W}}-1)$ pair.

######  Property 13.

Either $\textit{lPmax}[0,...,fi]={\sf l_{p}}[0,...,fi]$ or
$\textit{rPmax}[0,...,fi]={\sf r_{p}}[0,...,fi]$.

###### Proof.

Suppose that one of these paths don’t passes through intersection of ${\sf
l_{p}}$ and ${\sf r_{p}}$, WLOG let it be rPmax. Then rPmax don’t intersect
${\sf l_{p}}$. Then, due to Property 5.2, we get $\textit{lPmax}={\sf l_{p}}$.
I.e. $\textit{lPmax}[0,...,fi]={\sf l_{p}}[0,...,fi]$.

It remains to consider when lPmax intersect ${\sf r_{p}}$ in some $i_{1}$-th
row and rPmax intersect ${\sf l_{p}}$ in some $i_{2}$-th row. By Note 7
$fi\leq\min\\{i_{1},i_{2}\\}$. WLOG let $i_{1}<i_{2}$, then due to Property
5.1 we get $\textit{lPmax}[0,...,i_{1}]={\sf l_{p}}[0,...,i_{1}]$. Since
$fi\leq i_{1}$, then $\textit{lPmax}[0,...,fi]={\sf l_{p}}[0,...,fi]$. ∎

Using Lemma 2 it is enough to find ${\sf lrdtms}(0,0,W-1)$ pair lPmax and
rPmax. Also, due to Property 13 either $\textit{lPmax}(fi)=fj$ or
$\textit{rPmax}(fi)=fj$.

WLOG let $\textit{lPmax}(fi)=fj$. Let $maxPath(i,j)$ is path $p$ from
$(0,{\textit{W}}-1)$ to $(i,j)$ with maximum sum. Then, using Property 13, it
is enough to find maximum of

${\sf PS}({\sf l_{p}}[...,fi-1])+{\sf PS}(lp_{j})+{\sf
PS}(rp_{j})+maxPath(fi,j)-g_{fi,j}$

for each $j>fj$, where $lp_{j}$ and $rp_{j}$ are ${\sf lrdtms}(fi,fj,j)$ pair.

Sum of ${\sf lrdtms}(fi,fj,j)$ pair equal to ${\sf{M_{l}}}(fi,j)$. For
calculation of $maxPath(fi,j)$ for each $j>fj$ let consider next tables

######  Definition 19.

Let $tg$ is grid:

$tg_{i,j}=\begin{cases}-\infty&i\geq fi\ or\ i<j<{\textit{W}}-1-i,\\\ {\sf
g}_{i,j}&i<fi\ and\ (j\leq i\ or\ j\geq{\textit{W}}-1-i).\end{cases}$

######  Definition 20.

for $j=0,...{\textit{W}}{-}1$ the $udF_{i,j}(g^{\prime})$ is table defined
under grid $g^{\prime}$ as:

$udF_{i,j}(g^{\prime})=\begin{cases}g^{\prime}_{i,j}&i=0,\\\
g^{\prime}_{i,j}+\max\\{udF_{i-1,j-1}(g^{\prime}),udF_{i-1,j}(g^{\prime}),udF_{i-1,j+1}(g^{\prime})\\}&i=1,...,{\textit{H}}-1.\end{cases}$

Similarly to ${\sf F}$ the $udF$ allows to find the path with maximum sum. For
$j<fj$ the $udF_{fi,j}(tg)$ gives sum of path with maximum sum between cells
$(fi,j)$ and $(0,0)$. And for $j>fj$ the $udF_{fi,j}(tg)$ gives maximum sum of
path between $(fi,j)$ and $(0,W-1)$. Thus $maxPath(fi,j)=udF_{fi,j}(tg)$ for
any $j>fj$.

Then, for solve our task we can find

$lMax=\max_{j=fj+1,...,{\textit{W}}-1}\\{{\sf{M_{l}}}(fi,j)+udF_{fi,j}(tg)-{\sf
g}_{fi,j}\\}+{\sf F}_{0,0}-{\sf F}_{fi-1,fj},$
$rMax=\max_{j=0,...,fj-1}\\{{\sf{M_{r}}}(fi,j)+udF_{fi,j}(tg)-{\sf
g}_{fi,j}\\}+{\sf F}_{0,{\textit{W}}-1}-{\sf F}_{fi-1,fj}.$

Then $\max\\{lMax,rMax\\}$ is required answer.

###  4.3 Linear solutions for some extensions

Let $0\leq d_{i}<{\textit{W}}$ for each $i>0$. Then rule (r1) can be extended
as

  * (r1’)

From cell $(i-1,j)$ robots can move to cell $(i,j-d_{i})$, $(i,j-d_{i}+1)$, …
or $(i,j+d_{i})$.

Note that all Properties, Lemmas and Theorems can be generalized for extended
rule (r1’). Therefore further we assume that it is true.

The length of input data is the length of grid plus the length of vector $d$.
Thus, the length of input data is $\Theta({\textit{H}}\cdot{\textit{W}})$. Let
prove that there are LS i.e. with complexity
${\textit{O}}({\textit{H}}\cdot{\textit{W}})$.

Let $SWM_{v,w}(j)=\max\\{v(j-w),...,v(j+w)\\}$ where $v$ is vector.
$SWM_{v,w}$ is sliding window maximum (SWM) with window size $2w+1$. The SWM
is well known structure in programming, and can be defined as array of
maximums of each subarray of size $2w+1$ in $v$. SWM has
$\langle{\textit{O}}(|v|),{\textit{O}}(1)\rangle$ complexity. I.e. array
$SWM_{v,w}$ can be prepared in ${\textit{O}}(|v|)$, and (after preparing) the
value $SWM_{v,w}(j)$ can be obtained in ${\textit{O}}(1)$ for each $j$ (as in
[15]). Then ${\sf F}$ can be extended as

${\sf F}_{i,j}=\begin{cases}0&i={\textit{H}},\\\ {\sf
g}_{i,j}&i={\textit{H}}-1,\\\ {\sf g}_{i,j}+SWM_{R_{i+1,{\sf
F}},d_{i+1}}(j)&i=0,...,{\textit{H}}-2\end{cases}$

where $R_{i,{\sf F}}$ is vector of length ${\textit{W}}{+}2d_{i}$ such that

$R_{i,{\sf F}}(j)=\begin{cases}0&-d_{i}\leq j<0\ or\ {\textit{W}}\leq
j<{\textit{W}}+d_{i},\\\ {\sf F}_{i,j}&0\leq j<{\textit{W}}.\end{cases}$

Then each row for ${\sf F},R$ and $SWM$ can be found sequentially: the first
${\sf F}_{H,*}$, then
${\sf F}_{H{-}1,*}\rightarrow R_{H{-}1,{\sf F}}\rightarrow SWM_{R_{H{-}1,{\sf
F}},d_{H{-}1}}\rightarrow{\sf F}_{H{-}2,*}\rightarrow\cdots\rightarrow
R_{1,F}\rightarrow SWM_{R_{1,{\sf F}},d_{1}}\rightarrow{\sf F}_{0,*}$.

Since $SWM_{R_{i,{\sf F}},d_{i}}$ can be found in ${\textit{O}}({\textit{W}})$
for each $i$, then table ${\sf F}$ can be found in
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}})$.

Let prove that ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ can be found in
${\textit{O}}({\textit{H}}{\cdot}{\textit{W}})$.

Assume that $i,j,max_{1},max_{2}$ and $max_{3}$ are designations from
induction step of Lemma 1.

Let $b_{1}^{\prime}=\max\\{{\sf l_{p}}(i{-}1){-}d_{i},0\\}$ and
$b_{2}^{\prime}={\sf l_{p}}(i){-}1$.

Let $b_{1}^{\prime\prime}=\max\\{j{-}d_{i},{\sf r_{p}}(i),{\sf
l_{p}}(i){+}1\\}$ and
$b_{2}^{\prime\prime}=\min\\{j{+}d_{i},{\textit{W}}{-}1\\}$.

And let $b_{1}=\max\\{0,{\sf l_{p}}(i{-}1){-}d_{i}\\}=b_{1}^{\prime}$,
$b_{2}={\sf l_{p}}(i){-}1=b_{2}^{\prime}$ and $b_{3}=\max\\{{\sf
r_{p}}(i){+}1,j{-}d_{i}\\}$, $b_{4}=\min\\{j{+}d_{i},{\textit{W}}{-}1\\}$.

I.e. $b_{1}^{\prime},b_{2}^{\prime}$ are extended $b_{1},b_{2}$ from case 1 of
Lemma 1, $b_{1}^{\prime\prime},b_{2}^{\prime\prime}$ are extended
$b_{1},b_{2}$ from case 2, and $b_{1},b_{2},b_{3},b_{4}$ are extended
$b_{1},b_{2},b_{3},b_{4}$ from case 4.

$\max_{1}(j),max_{2}(j)$ and $max_{3}(j)$ can be found in ${\textit{O}}(1)$
using precalculated the SWM with window size $2d_{i}+1$ for $i$-th row of
${\sf{M_{l}}},{\sf{M_{r}}}$ and ${\sf F}$.

Let $M_{li}$ is vector defined between positions $b_{1}^{\prime\prime}-d_{i}$
and ${\textit{W}}+d_{i}$ such that $M_{li}(k)={\sf{M_{l}}}(i,k)$ for each
$b_{1}^{\prime\prime}\leq k<{\textit{W}}$, and $M_{li}(k)=0$ for each
$b_{1}^{\prime\prime}-d_{i}\leq k<b_{1}^{\prime\prime}$ and ${\textit{W}}\leq
k\leq{\textit{W}}+d_{i}$. Then

$max_{2}(j)=\max_{k=b^{\prime\prime}_{1},...,b^{\prime\prime}_{2}}\\{{\sf{M_{l}}}(i,k)\\}=SWM_{M_{li},d_{i}}(j).$

Let $M_{ri}=\max_{k=b^{\prime}_{1},...,b^{\prime}_{2}}\\{{\sf{M_{r}}}(i,k)\\}$
i.e. $max_{1}(j)=M_{ri}$ independ on $j$.

Let $F_{i}$ is vector defined between positions $b_{3}-d_{i}$ and
${\textit{W}}+d_{i}$ such that $F_{i}(k)={\sf F}(k)$ for each $b_{3}\leq
k<{\textit{W}}$, and $F_{i}(k)=0$ for each $b_{3}-d_{i}\leq k<b_{3}$ and
${\textit{W}}\leq k\leq{\textit{W}}+d_{i}$. Then

$max_{3}(j)=\max_{k=b_{1},...,b_{2}}\\{{\sf{M_{r}}}(i,k)\\}+\max_{k=b_{3},...,b_{4}}\\{{\sf
F}_{i,k}\\}-{\sf F}_{i,{\sf r_{p}}(i)}=M_{ri}+SWM_{F_{i},d_{i}}(j)-{\sf
F}_{i,{\sf r_{p}}(i)}.$

I.e. $max_{1}(j),max_{2}(j)$ and $max_{3}(j)$ can be found in
${\textit{O}}(1)$ with prepared $SWM_{M_{li},d_{i}},M_{ri}$ and
$SWM_{F_{i},d_{i}}$ for each $j$.

The $M_{ri}$ can be found in ${\textit{O}}({\textit{W}})$ and doesn’t depend
on $j$. I.e. $M_{ri}$ can be represented as structure with
$\langle{\textit{O}}({\textit{W}}),{\textit{O}}(1)\rangle$ complexity. The
$SWM$ can be found for $M_{li}$ and $F_{i}$ with window $2d_{i}+1$ in
${\textit{O}}({\textit{W}}+2d_{i})={\textit{O}}({\textit{W}})$ for any row.
I.e. $SWM_{F_{i},d_{i}}$ and $SWM_{M_{li},d_{i}}$ are structures with
$\langle{\textit{O}}({\textit{W}}),{\textit{O}}(1)\rangle$ complexity.

Thus every row of ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ can be found in
${\textit{O}}({\textit{W}})$. I.e. this extension can be solved in
${\textit{O}}({\textit{H}}\cdot{\textit{W}})$ i.e. has linear solution.

And another natural extension of CP2 we formulate as

######  Conjecture 1.

Let $n>0$ and ${\textit{W}}\geq n$. And let there are $n$ robots located on
different cells in the top row of ${\sf g}$, which moves by rules (r1), (r2)
and (r3) to bottom row. Then exists an algorithm for finding the maximum
number of cherries, that can be collected by these robots, in
${\textit{O}}({\textit{H}}\cdot{\textit{W}}\cdot 2^{n})$.

For $n=1$ using ${\sf F}_{0,j}({\sf g})$ we get a proof of this Conjecture
immediately for robot at $j$-th column.

For $n=2$ let robots starts from $j_{1}$ and $j_{2}$ columns where
$j_{1}<j_{2}$. Consider 2 cases:

  1. 1.

When $j_{2}-j_{1}>2{\textit{H}}$ then any paths of robots don’t intersect with
each other. Then this case can be reduced to sum of 2 independent solutions
for $n=1$.

  2. 2.

$j_{2}-j_{1}\leq 2{\textit{H}}$ then all reachable columns by these robots in
interval from $j_{1}-{\textit{H}}$ to $j_{2}+{\textit{H}}$. Then we can get
subgrid of size ${\textit{H}}{\times}(4{\textit{H}})$ contains this interval
of all reachable columns. Let denote this subgrid as ${\sf g}_{d}$. Let ${\sf
g}_{u}$ is grid of size $(2{\textit{H}}){\times}(4{\textit{H}})$ with zeros.
Then let ${\sf g}^{\prime}$ obtained by attaching the ${\sf g}_{u}$ under the
${\sf g}_{d}$. Thus, we get ${\sf g}^{\prime}$ of size
$(3{\textit{H}}){\times}(4{\textit{H}})$.

Now let $m$ is maximum value of ${\sf g}^{\prime}$. Then let ${\sf
g}^{\prime\prime}$ is ${\sf g}^{\prime}$ but with increased values by
$m\cdot{\textit{H}}$ in cells $(2{\textit{H}},j_{1})$ and
$(2{\textit{H}},j_{2})$. Then after applying our LS for ${\sf
g}^{\prime\prime}$ we get the sum of 2 DP, passes through the cells
$(2{\textit{H}},j_{1})$ and $(2{\textit{H}},j_{2})$ with maximum sum M. Then
required value is $M-2m\cdot{\textit{H}}$.

Thus, we reduce the case $n=2$ to CP2 by linear time. Then using Theorem 1 we
confirm our Conjecture for $n=2$.

## References

  * [1] “1463. Cherry Pickup II”. (n.d.). In leetcode.com. Retrieved 14 Mar, 2021, from: https://leetcode.com/problems/cherry-pickup-ii/.
  * [2] “931. Minimum Falling Path Sum”. (n.d.). In leetcode.com. Retrieved 14 Mar, 2021, from: https://leetcode.com/problems/minimum-falling-path-sum/.
  * [3] “Gold Mine Problem”. (n.d.). In tutorialspoint.dev. Retrieved 14 Mar, 2021, from: https://tutorialspoint.dev/algorithm/dynamic-programming-algorithms/gold-mine-problem
  * [4] “64. Minimum Path Sum”. (n.d.). In leetcode.com. Retrieved 14 Mar, 2021, from: https://leetcode.com/problems/minimum-path-sum/.
  * [5] “741. Cherry Pickup”. (n.d.). In leetcode.com. Retrieved 14 Mar, 2021, from: https://leetcode.com/problems/cherry-pickup/.
  * [6] “SumoLogic Interview Question for SDE-3s”. (2015, 9 Aug). In careercup.com. Retrieved 14 Mar, 2021, from: https://www.careercup.com/question?id=5653217876639744.
  * [7] Scheffler P., “A Practical Linear Time Algorithm for Disjoint Paths in Graphs with Bounded Tree-width”. Report 396, Fachbereich 3 Mathematik, TU Berlin, 1994.
  * [8] Golovach P. A., Kolliopoulos S. G., Stamoulis G., Thilikos D. M., “Planar Disjoint Paths in Linear Time”. arXiv:1907.05940 [cs.DS], 2019.
  * [9] Tholey T., “Linear time algorithms for two disjoint paths problems on directed acyclic graphs”. TCS, vol. 465, pp. 35-48, 2012. doi:10.1016/j.tcs.2012.09.025.
  * [10] Suurballe J. W., “Disjoint paths in a network”. Netw., vol. 4, pp. 125-145, 1974. doi:10.1002/net.3230040204.
  * [11] Dijkstra, E. W., “A note on two problems in connexion with graphs”. Numerische Mathematik, 1(1):269-271, 1959. doi:10.1007/BF01386390.
  * [12] Fredman M.L., Tarjan R.E., “Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms”. J. ACM, 34(3):596–615, 1987. doi:10.1109/SFCS.1984.715934.
  * [13] Ahuja R.K.,Mehlhorn K.,Orlin J.B., Tarjan R.E., “Faster Algorithms for the Shortest Path Problem”. J. ACM, 37(2):213-223, 1990. doi:10.1145/77600.77615.
  * [14] “Shortest Path in Directed Acyclic Graph”. (n.d.). In tutorialspoint.dev. Retrieved 30 Mar, 2021, from: https://tutorialspoint.dev/data-structure/graph-data-structure/shortest-path-for-directed-acyclic-graphs.
  * [15] “Sliding Window Maximum (Maximum of all subarrays of size k)”. (n.d.). In tutorialspoint.dev. Retrieved 14 Mar, 2021, from: https://tutorialspoint.dev/data-structure/queue-data-structure/sliding-window-maximum-maximum-of-all-subarrays-of-size-k.

Listing 1: Search for maximums table for single robot (tested)

⬇

1import numpy as np

2

3def get_F(g):

4 H = len(g)

5 W = len(g[0])

6 F = np.empty((H, W)) # create table HxW

7

8 F[H-1] = g[H-1].copy() # copy last row

9

10 for i in reversed(np.arange(0, H-1)):#i = H-2, …, 0

11 F[i][0] = g[i][0] + max(F[i+1][0], F[i+1][1])

12 F[i][W-1] = g[i][W-1] + max(F[i+1][W-2], F[i+1][W-1])

13 for j in np.arange(1, W-1): # j = 1, …, W-2

14 F[i][j] = g[i][j] + max(F[i+1][j-1], F[i+1][j], F[i+1][j+1])

15

16 return F

Listing 2: Search for ${\sf l_{p}}$ and ${\sf r_{p}}$ (tested)

⬇

1def get_bounds(F):

2 H = len(F)

3 W = len(F[0])

4 lp = np.arange(0, H)# lp = [0, …, H-1]

5 rp = np.arange(0, H)# rp = [0, …, H-1]

6

7 lp[0] = 0

8 rp[0] = W - 1

9

10 for i in np.arange(1, H): # i = 1, …, H-1

11 lj = lp[i] = lp[i-1]

12 if lj > 0 and F[i][lj-1] >= F[i][lj]:

13 lp[i] = lj - 1

14 if lj < W-1 and F[i][lp[i]] < F[i][lj+1]:

15 lp[i] = lj + 1

16

17 rj = rp[i] = rp[i-1]

18 if rj < W-1 and F[i][rj+1] >= F[i][rj]:

19 rp[i] = rj + 1

20 if rj > 0 and F[i][rp[i]] < F[i][rj-1]:

21 rp[i] = rj - 1

22

23 return lp, rp

Listing 3: Search for ${\sf{M_{l}}}$ and ${\sf{M_{r}}}$ tables (short version.
tested)

⬇

1def get_max(fromk, tok, Table, i):

2 _max = float(’-inf’)

3 for k in np.arange(fromk, tok+1):# k = fromk,…,tok

4 _max = max(_max, Table[i][k])

5 return _max

6

7def get_M(g, F, lp, rp):

8 H, W = len(F), len(F[0])

9 Ml, Mr = np.empty((H, W)), np.empty((H, W))

10

11 # base case M*[H-1]

12 lj = max(rp[H-1], lp[H-1]+1)

13 for j in np.arange(lj, W): # j = max(rp[H-1], lp[H-1]+1),…,W-1

14 Ml[H-1][j] = g[H-1][lp[H-1]] + g[H-1][j]

15

16 rj = min(lp[H-1], rp[H-1]-1)

17 for j in np.arange(0, rj+1):# j = 0,…,min(lp[H-1], rp[H-1]-1)

18 Mr[H-1][j] = g[H-1][rp[H-1]] + g[H-1][j]

19

20 # induction step M*[0,…,H-2]

21 for i in reversed(np.arange(0, H-1)): # i = H-2,…,0

22 Mri = get_max(max(0, lp[i]-1), lp[i+1]-1, Mr, i+1)

23 Mli = get_max(rp[i+1]+1, min(W-1, rp[i]+1), Ml, i+1)

24

25 # Ml[i] search

26 for j in np.arange(max(lp[i]+1,rp[i]), W):

27 max1, max2 = 0, 0

28

29 # case lPmax(i+1)<lp(i+1)

30 if max(lp[i],1) <= lp[i+1]:

31 max1 = get_max(max(rp[i+1], j-1), min(j+1, W-1),

32 F, i+1) + Mri - F[i+1][rp[i+1]]

33

34 # case lPmax(i+1)=lp(i+1)

35 if lp[i+1]+2 <= W:

36 max2 = get_max(max(j-1, rp[i+1], lp[i+1]+1),

37 min(j+1, W-1),

38 Ml, i+1)

39

40 Ml[i][j] = g[i][lp[i]] + g[i][j] + max(max1,max2)

41

42 # Mr[i] search

43 for j in np.arange(0, min(lp[i],rp[i]-1)+1):

44 max1, max2 = 0, 0

45

46 # case rPmax(i+1)>rp(i+1)

47 if rp[i+1] <= min(W-2,rp[i]):

48 max1 = get_max(max(0, j-1), min(j+1, lp[i+1]),

49 F, i+1) + Mli - F[i+1][lp[i+1]]

50

51 # case rPmax(i+1)=rp(i+1)

52 if 1 <= rp[i+1]:

53 max2 = get_max(max(j-1, 0),

54 min(j+1, lp[i+1], rp[i+1]-1),

55 Mr, i+1)

56

57 Mr[i][j] = g[i][rp[i]] + g[i][j] + max(max1,max2)

58

59 return Ml, Mr

Listing 4: Main algorithm (tested)

⬇

1def Pickup_Cherries_II(grid):

2 W = len(grid[0])

3 F = get_F(grid)

4 lp, rp = get_bounds(F)

5 Ml, Mr = get_M(grid, F, lp, rp)

6

7 return Ml[0][W-1]