Maximum subarray problem with weights 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&lt;=i&lt;=j&lt;=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&lt;j$. 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 &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

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?
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 on Monge matrices):
Lemma 1. For any $(i, j)$ and $(k, \ell)$ in $I$ such that $i&lt;k$ and $j &lt; \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 &gt; i$, and $j&lt;\ell$ so $W[j] \le W[\ell]$.  This proves Lemma 1. $~~~\Box$
It is well-known (e.g. Section 3.7 of this survey) 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&lt;k$ and $j &lt; \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. (It would if $M$ 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. 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 &lt; i \le n$.  Then we no longer require the &quot;upper triangular&quot; assumption: the property in Corollary 2 holds for all pairs $(i, j)$ and $(k, \ell)$ with $(1,1) \le (i, j) &lt; (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 of the SMAWK algorithm by David Eppstein.  I adapted his code to solve your problem; here is my adaptation.