0
$\begingroup$

We are given an array $A[1..n]$. We don't have direct access to $A$, but we can query what is the sum of $A[i..j]$ for every interval $i..j$. We would like to find the maximum of $A[i..j]$ over all intervals $i..j$. How can we prove that we must make $\Omega(n\log n)$ queries?

My thought is that we can solve the problem in $O(n\log n)$ using divide and conquer. Roughly speaking, for any $1\leq i\leq j\leq n$ we can recurse on $i\dots\frac{j}{2}$, and $\frac{j}{2}+1\dots j$, return the maximum of one of the two halves or the sum of the two halves, resulting in a running time of $O(n)$. I don't think that my idea works, and I don't know why there should be at least $\Omega(n \log n)$ many queries. Any help would be appreciated.

$\endgroup$
1
  • 3
    $\begingroup$ You can compute $A[i]$ as the sum of the interval $A[i..i]$, so only $n$ queries are needed. $\endgroup$ Jul 30 at 11:33
2
$\begingroup$

You can solve your problem with $O(n)$ queries.

Let $Q(i,j)$ denote the result of a query on $A[i,j]$. This upper bound on the number of queries is trivial since you can always reconstruct $A$ with $n$ queries $Q(i,i)$ for $i=1,\dots,n$ and then solve your problem on $A$ with any algorithm (regardless of its running time).

The following greedy algorithm additionally shows that $O(n)$ time (and hence queries) suffices.

  • $i \gets 1$.

  • Store $(1,1)$ as a candidate solution

  • For $j=2,\dots,n$:

    • If $Q(i,j) \le Q(j,j)$ then $i \gets j$.
    • Store $(i,j)$ as a candidate solution
  • Return the candidate solution $(i,j)$ that maximizes $Q(i,j)$.

We now prove that the algorithm must be correct. I'm assuming that we cannot return an empty subarray (if this is not the case, it is easy to modify the algorithm and the proof). It suffices to show that an optimal solution must belong to the set of the candidate solutions.

Immediately before the first iteration of the for loop $A[1,1]$ is the (unique) maximum-sum contiguous subarrays of $A$ ending with index $1$. We now show by induction that when an iteration of the for loop is completed, we have that $A[i,j]$ is the maximum-sum contiguous subarrays of $A$ ending with index $j$ and maximizing $i$.

Let $(i',j)$ denote the maximum-sum contiguous subarrays of $A$ ending with index $j$ and maximizing $i'$. We will show that, at the end of the iteration, we must have $i=i'$. Either $i'=j$ or $i'<j$. If $i'=j$ then we necessarily have $Q(h,j) \le Q(j,j)$ for all $h=1,\dots,i-1$. This means that the "if" condition is satisfied and the algorithm sets $i$ to $j=i'$. Otherwise $i'<j$ and hence $A(i', j-1)$ is the maximum-sum contiguous subarrays of $A$ ending with index $j-1$ and maximizing $i'$ (otherwise a cut-and-paste argument yields a contradiction), showing that when the "if" statement is evaluated we have $i=i'$. Moreover $i'<j$ implies that $Q(i',j) < Q(j,j)$ showing that the condition of the "if" statement is not satisfied and $i$ is left unchanged in the considered iteration.

The correctness of the algorithm follows since there is necessarily some optimal soltion $A[i,j]$ such that $Q(h,j) < Q(i,j)$ for all $h=i+1, \dots, j$.

$\endgroup$

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.