3
$\begingroup$

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<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 > 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?

$\endgroup$
0
5
$\begingroup$

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<k$ 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) 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<k$ 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. (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 of the SMAWK algorithm by David Eppstein. I adapted his code to solve your problem; here is my adaptation.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ – Joris Kinable Aug 17 '20 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.