<p>Please check the following proof, and see the final remark with a link to code for an <span class="math-container">$O(n)$</span>-time algorithm.</p>
<p><strong>Theorem 1.</strong> <em>There is an <span class="math-container">$O(n\log n)$</span>-time algorithm for the problem.</em></p>
<p><em>Proof.</em>
Fix an instance <span class="math-container">$(n, A, W)$</span> of the problem. Define index set <span class="math-container">$I = \{(i, j) : 1\le i\le j \le n\}$</span>. The goal is to compute <span class="math-container">$\max_{(i,j)\in I} M_{ij}$</span>, where
<span class="math-container">$$\textstyle M_{ij} = \Big(\sum_{h=i}^j A[h]\Big) - (j-i+1) W[j].$$</span></p>
<p>Observe that <span class="math-container">$M_{ij}$</span> has the (upper-triangular) inverse Monge property (see e.g. <a href="https://doi.org/10.1016/0166-218X(95)00103-X" rel="noreferrer">this survey</a> on Monge matrices):</p>
<p><strong>Lemma 1.</strong> <em>For any <span class="math-container">$(i, j)$</span> and <span class="math-container">$(k, \ell)$</span> in <span class="math-container">$I$</span> such that <span class="math-container">$i&lt;k$</span> and <span class="math-container">$j &lt; \ell$</span>,</em> <span class="math-container">$$M_{i\ell} - M_{ij} \le M_{k\ell} - M_{kj}.$$</span></p>
<p><em>Proof of Lemma 1.</em>  By calculation,</p>
<p><span class="math-container">$$M_{i\ell} - M_{ij} = \Big(\sum_{h={j+1}}^\ell A[h]\Big) + (j-i+1) W[j] - (\ell-i+1) W[\ell],$$</span>
while
<span class="math-container">$$M_{k\ell} - M_{kj} = \Big(\sum_{h={j+1}}^\ell A[h]\Big) + (j-k+1) W[j] - (\ell-k+1) W[\ell],$$</span>
so
<span class="math-container">$$(M_{i\ell} - M_{ij}) - (M_{k\ell} - M_{kj}) =
(k-i) W[j] - (k - i) W[\ell] = (k-i)(W[j] - W[\ell]),$$</span>
which is non-positive as <span class="math-container">$k &gt; i$</span>, and <span class="math-container">$j&lt;\ell$</span> so <span class="math-container">$W[j] \le W[\ell]$</span>.  This proves Lemma 1. <span class="math-container">$~~~\Box$</span></p>
<p>It is well-known (e.g. Section 3.7 of <a href="https://doi.org/10.1016/0166-218X(95)00103-X" rel="noreferrer">this survey</a>) that the Monge property is sufficient to obtain a simple <span class="math-container">$O(n\log n)$</span>-time algorithm, and it is easy to adapt that algorithm to the upper-triangular case.  For completeness I'll sketch the algorithm here.</p>
<p>Lemma 1 implies that <span class="math-container">$M$</span> is (upper-triangular) totally (inverse) monotone:</p>
<p><strong>Corollary 1.</strong> <em>For any <span class="math-container">$(i, j)$</span> and <span class="math-container">$(k, \ell)$</span> in <span class="math-container">$I$</span> such that <span class="math-container">$i&lt;k$</span> and <span class="math-container">$j &lt; \ell$</span>, if <span class="math-container">$M_{ij} \le M_{i\ell}$</span> then <span class="math-container">$M_{kj} \le M_{kl}$</span>.</em></p>
<p>For <span class="math-container">$1\le i \le n$</span>, define <span class="math-container">$J(i) = \arg\max_{j} M_{ij}$</span> to be the column index of the maximum entry in row <span class="math-container">$i$</span>.  Corollary 1 implies the following additional corollary:</p>
<p><strong>Corollary 2.</strong> <span class="math-container">$J(1) \le J(2) \le \cdots \le J(n)$</span></p>
<p>The algorithm computes <span class="math-container">$J(i)$</span> for the middle row <span class="math-container">$i=\lfloor n/2 \rfloor$</span> in <span class="math-container">$O(n)$</span> time (having precomputed all partial sums of <span class="math-container">$A$</span> in <span class="math-container">$O(n)$</span> time, so that the value of any given <span class="math-container">$M_{ij}$</span> can be computed in constant time), then subdivides <span class="math-container">$M$</span> into four quadrants around the point <span class="math-container">$(i, J(i))$</span>, recurses on the upper-left and lower-right quadrants, and takes either <span class="math-container">$(i, J(i))$</span> or one of the two points returned recursively, whatever is best.</p>
<p>(Note that the algorithm does not explicitly construct all of <span class="math-container">$M$</span>.  In fact, it examines <span class="math-container">$O(n\log n)$</span> entries of <span class="math-container">$M$</span>.)</p>
<p>By Corollary 2, the maximum cannot be in the upper-right or lower-left quadrant, so the algorithm is correct.</p>
<p>Letting <span class="math-container">$T(n, m)$</span> denote the worst-case runtime on an <span class="math-container">$n\times m$</span> index set, we have <span class="math-container">$$T(n, m) \le m + \max_{1\le j\le m} ~T(\lfloor n/2 \rfloor -1, j) + T(n - \lfloor n/2\rfloor, m-j+1)$$</span>
and <span class="math-container">$T(1, m) \le m$</span>.  For any execution of the algorithm, the recursion tree has <span class="math-container">$O(\log n)$</span> levels. Within a given level, letting <span class="math-container">$(n_j, m_j)$</span> denote the dimensions of the <span class="math-container">$j$</span>th subproblem on that level, we have <span class="math-container">$\sum_j m_j = O(m)$</span>, from which it follows that the total work for all subproblems on that level (outside of their recursive calls) is <span class="math-container">$O(m)$</span>, so that <span class="math-container">$T(n, m) = O(m\log n)$</span>. (This can also be easily verified by induction.) So the run-time of the top-level call is <span class="math-container">$T(n, n) = O(n\log n)$</span>. <span class="math-container">$~~~\Box$</span></p>
<p><strong>Remarks.</strong> The total monotonicity of <span class="math-container">$M$</span> (Corollary 1 above) probably also implies an <span class="math-container">$O(n)$</span>-time algorithm via <a href="https://en.wikipedia.org/wiki/SMAWK_algorithm" rel="noreferrer">the SMAWK algorithm</a>. (It would if <span class="math-container">$M$</span> was totally (inverse) monotone, instead of just &quot;upper-triangular&quot; totally inverse monotone.)  I don't know whether SMAWK applies in this case, but I'd guess so. <em>EDIT: See comment below.</em></p>
<p>Note that the above proof requires neither the assumption <span class="math-container">$A[i] \ge W[i]$</span>, nor the non-negativity of the <span class="math-container">$A[i]$</span>'s and <span class="math-container">$W[i]$</span>'s.</p>
<p><strong>EDIT:</strong> It seems to me that we can extend <span class="math-container">$M$</span> to make it totally inverse Monge simply by taking <span class="math-container">$M_{ij}$</span> to be, say, <span class="math-container">$-n W[n]$</span>, for <span class="math-container">$1\le j &lt; i \le n$</span>.  Then we no longer require the &quot;upper triangular&quot; assumption: the property in Corollary 2 holds for all pairs <span class="math-container">$(i, j)$</span> and <span class="math-container">$(k, \ell)$</span> with <span class="math-container">$(1,1) \le (i, j) &lt; (k, \ell) \le (n, n)$</span>.  That is, <span class="math-container">$M$</span> extended in this way is totally (inverse) monotone. So the SMAWK algorithm can be applied to this <span class="math-container">$M$</span> to solve the problem in <span class="math-container">$O(n)$</span> time.</p>
<p>A quick google search gives <a href="http://code.activestate.com/recipes/117244-smawk-totally-monotone-matrix-searching-algorithm/" rel="noreferrer">this Python implementation</a> of the SMAWK algorithm by David Eppstein.  I adapted his code to solve your problem; <a href="https://repl.it/repls/AuthenticUnknownCamel#main.py" rel="noreferrer">here</a> is my adaptation.</p>

CC BY-SA 4.0
2020-08-17T21:32:14.200Z
Thank you for your very detailed response! It will take me some time to analyse this in detail is I'm (not yet) familiar with Monge matrices. The concept of these matrices is quite abstract and takes some time to get into. The survey paper you cited is very helpful! The thoughtfulness of your answers is really amazing.
Joris Kinable
CC BY-SA 4.0
2020-08-15T17:59:29.343Z
2020-08-17T14:25:30.097Z
2020-08-17T14:25:30.097Z
Neal Young
<p>The <a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem" rel="nofollow noreferrer">maximum sum subarray problem</a> involves finding a contiguous subarray with the largest sum, within a given one-dimensional array <span class="math-container">$A[1...n]$</span> of numbers. Formally, the task is to find indices i and j with <span class="math-container">$1&lt;=i&lt;=j&lt;=n$</span> s.t. the sum <span class="math-container">$\sum_{x=i}^j A[x]$</span> is as large as possible.
It is well-known that this problem can be solved in linear time <span class="math-container">$O(n)$</span>.</p>
<p>I'm trying to solve a variation of this particular problem. In addition to array <span class="math-container">$A[1...n]$</span> we are also given an array <span class="math-container">$W[1...n]$</span> where <span class="math-container">$W[i]$</span> gives the weight of the ith item. The items are ordered in increasing weight, so <span class="math-container">$W[i] \leq W[j]$</span> if <span class="math-container">$i&lt;j$</span>. Moreover, all values in <span class="math-container">$W$</span> and <span class="math-container">$A$</span> are larger than 0, and <span class="math-container">$A[i] \geq W[i]$</span> for all <span class="math-container">$i=1...n$</span>. Objective: find a contiguous subarray that maximizes <span class="math-container">$\sum_{x=i}^j (A[x]-W[j])$</span>.</p>
<p>Here's a numerical example</p>
<pre><code>i  W  A
1  6  14
2  7  12
3  8  10
4  9  10
5  12 18
6  13 16
7  14 25
8  18 22
9  19 26
10 20 23
</code></pre>
<p>The solution to the above example would be: i=5, j=7, with a score of: <span class="math-container">$A[5]-W[7]+A[6]-W[7]+A[7]-W[7]=18-14+16-14+25-14=17$</span>
To solve this problem, I came up with the following <span class="math-container">$O(n²)$</span> algorithm:</p>
<pre><code>best_score= -1
best_i = best_j = -1

for j=n..1:
  score=0
  for i=j..1:
    score=score + A[i]-W[j];
    
    if score &gt; best_score:
      best_score=score
      best_i = i;
      best_j = j;
    if score &lt; 0:
      continue; //skip inner loop and continue with outer loop
</code></pre>
<p>Can this problem be solved more efficiently than O(n²)? In particular, can you prune part of the search by using the best score you found thus far?</p>

<ds.algorithms>
Maximum subarray problem with weights
Joris Kinable
# Maximum subarray problem with weights

(Asked by: username_0 on 2020-08-15)

The maximum sum subarray problem involves finding a contiguous subarray with the largest sum, within a given one-dimensional array $A[1...n]$ of numbers. Formally, the task is to find indices i and j with $1<=i<=j<=n$ s.t. the sum $\sum_{x=i}^j A[x]$ is as large as possible.
It is well-known that this problem can be solved in linear time $O(n)$.
I'm trying to solve a variation of this particular problem. In addition to array $A[1...n]$ we are also given an array $W[1...n]$ where $W[i]$ gives the weight of the ith item. The items are ordered in increasing weight, so $W[i] \leq W[j]$ if $i. Moreover, all values in $W$ and $A$ are larger than 0, and $A[i] \geq W[i]$ for all $i=1...n$. Objective: find a contiguous subarray that maximizes $\sum_{x=i}^j (A[x]-W[j])$.
Here's a numerical example
i  W  A
1  6  14
2  7  12
3  8  10
4  9  10
5  12 18
6  13 16
7  14 25
8  18 22
9  19 26
10 20 23

The solution to the above example would be: i=5, j=7, with a score of: $A[5]-W[7]+A[6]-W[7]+A[7]-W[7]=18-14+16-14+25-14=17$
To solve this problem, I came up with the following $O(n²)$ algorithm:
best_score= -1
best_i = best_j = -1

for j=n..1:
  score=0
  for i=j..1:
    score=score + A[i]-W[j];
    
    if score > best_score:
      best_score=score
      best_i = i;
      best_j = j;
    if score < 0:
      continue; //skip inner loop and continue with outer loop

Can this problem be solved more efficiently than O(n²)? In particular, can you prune part of the search by using the best score you found thus far?

**Tags:** ds.algorithms


---

## 1 answers

### Answer by username_1 on 2020-08-15. Score: 5 | Accepted answer

Please check the following proof, and see the final remark with a link to code for an $O(n)$-time algorithm.

**Theorem 1.** *There is an $O(n\log n)$-time algorithm for the problem.*

*Proof.*
Fix an instance $(n, A, W)$ of the problem. Define index set $I = \{(i, j) : 1\le i\le j \le n\}$. The goal is to compute $\max\_{(i,j)\in I} M\_{ij}$, where
$$\textstyle M\_{ij} = \Big(\sum\_{h=i}^j A[h]\Big) - (j-i+1) W[j].$$

Observe that $M\_{ij}$ has the (upper-triangular) inverse Monge property (see e.g. [this survey](https://doi.org/10.1016/0166-218X(95)00103-X) on Monge matrices):

**Lemma 1.** *For any $(i, j)$ and $(k, \ell)$ in $I$ such that $i and $j < \ell$,* $$M\_{i\ell} - M\_{ij} \le M\_{k\ell} - M\_{kj}.$$

*Proof of Lemma 1.* By calculation,

$$M\_{i\ell} - M\_{ij} = \Big(\sum\_{h={j+1}}^\ell A[h]\Big) + (j-i+1) W[j] - (\ell-i+1) W[\ell],$$
while
$$M\_{k\ell} - M\_{kj} = \Big(\sum\_{h={j+1}}^\ell A[h]\Big) + (j-k+1) W[j] - (\ell-k+1) W[\ell],$$
so
$$(M\_{i\ell} - M\_{ij}) - (M\_{k\ell} - M\_{kj}) =
(k-i) W[j] - (k - i) W[\ell] = (k-i)(W[j] - W[\ell]),$$
which is non-positive as $k > i$, and $j<\ell$ so $W[j] \le W[\ell]$. This proves Lemma 1. $~~~\Box$

It is well-known (e.g. Section 3.7 of [this survey](https://doi.org/10.1016/0166-218X(95)00103-X)) that the Monge property is sufficient to obtain a simple $O(n\log n)$-time algorithm, and it is easy to adapt that algorithm to the upper-triangular case. For completeness I'll sketch the algorithm here.

Lemma 1 implies that $M$ is (upper-triangular) totally (inverse) monotone:

**Corollary 1.** *For any $(i, j)$ and $(k, \ell)$ in $I$ such that $i and $j < \ell$, if $M\_{ij} \le M\_{i\ell}$ then $M\_{kj} \le M\_{kl}$.*

For $1\le i \le n$, define $J(i) = \arg\max\_{j} M\_{ij}$ to be the column index of the maximum entry in row $i$. Corollary 1 implies the following additional corollary:

**Corollary 2.** $J(1) \le J(2) \le \cdots \le J(n)$

The algorithm computes $J(i)$ for the middle row $i=\lfloor n/2 \rfloor$ in $O(n)$ time (having precomputed all partial sums of $A$ in $O(n)$ time, so that the value of any given $M\_{ij}$ can be computed in constant time), then subdivides $M$ into four quadrants around the point $(i, J(i))$, recurses on the upper-left and lower-right quadrants, and takes either $(i, J(i))$ or one of the two points returned recursively, whatever is best.

(Note that the algorithm does not explicitly construct all of $M$. In fact, it examines $O(n\log n)$ entries of $M$.)

By Corollary 2, the maximum cannot be in the upper-right or lower-left quadrant, so the algorithm is correct.

Letting $T(n, m)$ denote the worst-case runtime on an $n\times m$ index set, we have $$T(n, m) \le m + \max\_{1\le j\le m} ~T(\lfloor n/2 \rfloor -1, j) + T(n - \lfloor n/2\rfloor, m-j+1)$$
and $T(1, m) \le m$. For any execution of the algorithm, the recursion tree has $O(\log n)$ levels. Within a given level, letting $(n\_j, m\_j)$ denote the dimensions of the $j$th subproblem on that level, we have $\sum\_j m\_j = O(m)$, from which it follows that the total work for all subproblems on that level (outside of their recursive calls) is $O(m)$, so that $T(n, m) = O(m\log n)$. (This can also be easily verified by induction.) So the run-time of the top-level call is $T(n, n) = O(n\log n)$. $~~~\Box$

**Remarks.** The total monotonicity of $M$ (Corollary 1 above) probably also implies an $O(n)$-time algorithm via [the SMAWK algorithm](https://en.wikipedia.org/wiki/SMAWK_algorithm). (It would if $M$ was totally (inverse) monotone, instead of just "upper-triangular" totally inverse monotone.) I don't know whether SMAWK applies in this case, but I'd guess so. *EDIT: See comment below.*

Note that the above proof requires neither the assumption $A[i] \ge W[i]$, nor the non-negativity of the $A[i]$'s and $W[i]$'s.

**EDIT:** It seems to me that we can extend $M$ to make it totally inverse Monge simply by taking $M\_{ij}$ to be, say, $-n W[n]$, for $1\le j < i \le n$. Then we no longer require the "upper triangular" assumption: the property in Corollary 2 holds for all pairs $(i, j)$ and $(k, \ell)$ with $(1,1) \le (i, j) < (k, \ell) \le (n, n)$. That is, $M$ extended in this way is totally (inverse) monotone. So the SMAWK algorithm can be applied to this $M$ to solve the problem in $O(n)$ time.

A quick google search gives [this Python implementation](http://code.activestate.com/recipes/117244-smawk-totally-monotone-matrix-searching-algorithm/) of the SMAWK algorithm by David Eppstein. I adapted his code to solve your problem; [here](https://repl.it/repls/AuthenticUnknownCamel#main.py) is my adaptation.

> **Comments:**
> **username_0**: Thank you for your very detailed response! It will take me some time to analyse this in detail is I'm (not yet) familiar with Monge matrices. The concept of these matrices is quite abstract and takes some time to get into. The survey paper you cited is very helpful! The thoughtfulness of your answers is really amazing.  

---

