1
$\begingroup$

Consider this post, the problem is 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$.

That answer describe an algorithm that solve the problem with at most $O(n)$ query, but the question is, what is the lower bound of number queries we need to find largest continuous sub array? Can we claim that $\Omega(n)$ queries is necessary?

$\endgroup$
2
  • $\begingroup$ Imagine all elements to have value zero. $\endgroup$
    – greybeard
    Apr 19, 2022 at 16:27
  • $\begingroup$ @greybeard How this help us? Could you explain more? $\endgroup$
    – ErroR
    Apr 19, 2022 at 21:29

3 Answers 3

2
$\begingroup$

At least $n$ queries are needed in the worst case.$^*$ Consider an algorithm which receives the answer $0$ on any query. After $n-1$ queries, it learns that $\langle v^{(1)},A \rangle = \cdots = \langle v^{(n-1)},A \rangle = 0$, where $v^{(i)}$ is the vector corresponding to the $i$'th query. We can find a non-zero vector $u$ which is orthogonal to all of $v_1,\ldots,v_{n-1}$. Thus we could have $A = u$ or $A = -u$. We claim that an answer which is valid for $A = u$ is not valid for $A = -u$. Since the algorithm cannot tell these two cases apart, it cannot guarantee outputting a valid solution.

To prove the claim, suppose without loss of generality that $u$ contains a positive entry. Therefore any optimal solution $I$ for $u$ satisfies $\sum_{i \in I} u_i > 0$. In contrast, $\sum_{i \in I} (-u)_i < 0$. We now distinguish between two cases:

  • Case 1: Some entry of $u$ is non-positive. In this case, the optimal solution $J$ for $-u$ satisfies $\sum_{j \in J} (-u)_j \geq 0$, and so we are done.
  • Case 2: All entries of $u$ are positive. If $n > 1$, this means that the unique optimal solution for $u$ is $\{1,\ldots,n\}$, whereas all optimal solutions of $u$ are either singletons or the empty interval, if we allow it. If $n = 1$, then this argument breaks unless we allow the empty interval as a solution. Indeed, if $n = 1$ and we don't allow the empty interval, then no queries are needed. This is the reason for the asterisk above.

A similar approach shows that $n$ queries are needed always. Suppose that after $n-1$ queries, the algorithm learns that $\langle v^{(i)}, A \rangle = c_i$ for $i = 1,\ldots,n-1$. The space of solutions to these equations includes a line $\alpha u + w$ (here $\alpha$ is the parameter), where $u \neq 0$. For large positive $\alpha$, any optimal solution for $\alpha u + w$ is also an optimal solution for $u$. This is since if $\sum_{i \in I} u_i > \sum_{j \in J} u_j$ then $$ \sum_{i \in I} (\alpha u_i + w_i) - \sum_{j \in J} (\alpha u_j + w_j) = \alpha \left(\sum_{i \in I} u_i - \sum_{j \in J} u_j\right) + \left(\sum_{i \in I} w_i - \sum_{j \in J} w_j\right), $$ which is positive for large enough $\alpha$, say $\alpha > \alpha_{I,J}$. The claim follows since there are only finitely many pairs $I,J$. Similarly, for large negative $\alpha$, any optimal solution for $\alpha u + w$ is also an optimal solution for $-u$. Above we have shown that an optimal solution for $u$ cannot be an optimal solution for $-u$ (unless $n = 1$ and we do not allow the empty interval).

$\endgroup$
5
  • $\begingroup$ $ v^i=A[1..i]$? Or $v^i=A[i]$? $\endgroup$
    – ErroR
    Apr 19, 2022 at 21:16
  • $\begingroup$ No. It is the vector which represents the $i$'th query. It has the same length as $A$, and its entries are $0$ and $1$. Furthermore, the $1$s are consecutive. $\endgroup$ Apr 19, 2022 at 21:17
  • $\begingroup$ Thank you. Could you explain more about "We can find a non-zero vector u which is orthogonal to all of $v_1,…,v_{n−1}$."? $\endgroup$
    – ErroR
    Apr 19, 2022 at 21:18
  • $\begingroup$ That's linear algebra. $\endgroup$ Apr 19, 2022 at 21:19
  • $\begingroup$ Ooh:) I wasn't passed linear algebra course:). $\endgroup$
    – ErroR
    Apr 19, 2022 at 21:20
2
$\begingroup$

Assume that you perform less than $n$ queries, so obtain less than $n$ sums. The corresponding system of equations so obtained is indeterminate, leaving room for degrees of freedom to move the maximum at different places.

E.g. for $n=3$, assume we query $a+b=5$ and $b+c=4$. Then $a=5-b$, $c=4-b$ and $a+b+c=9-b$, with $b$ free. So with large positive $b$, the optimal sequence would be $b$ alone, and with large negative $b$, it would be $a+b+c$.

$\endgroup$
1
  • $\begingroup$ Upvoted. While Yuval's answer is great, this answer is easily understood. $\endgroup$
    – John L.
    Apr 21, 2022 at 11:50
1
$\begingroup$

For every 1 ≤ j < n: We must make a query ending in $A_j$ otherwise we cannot determine the largest sum.

Reason: Assume we determined all subarray sums for all subarrays not ending in $A_j$. If we increase $A_j$ by a huge amount and decrease $A_{j+1}$ by the same amount, then the largest subarray sum is for a subarray ending in $A_j$. But if we decrease $A_j$ by a huge amount and increases $A_{j+1}$ by the same amount, the largest subarray sum is NOT for a subarray ending in $A_j$. Both actions leave all the subarray sums that we queried unchanged, so we cannot determine the largest subarray sum without an interval ending at $A_j$.

We also need an interval containing $A_n$, because $A_n$_ could be very large or very small so it cannot be ignored. So n intervals are needed. And the intervals A[1..1], A[1..2], ..., A[1..n] are sufficient because we can calculate all subarray sums from these. Or we could take A[1..1], A[2..2], ..., A[n..n].

$\endgroup$
7
  • 1
    $\begingroup$ Suppose that $n = 3$ and you query $A[1],A[3],A[1]+A[2]+A[3]$. $\endgroup$ Apr 19, 2022 at 20:58
  • $\begingroup$ At the line "Reason: Assume we determined all subarray sums for all subarrays not ending in $A_j$", all sub arrays ony contains subarrays from $1$ to $j-1$? or contains sub arrays from $1$ to $j-1$ and $j+1$ to $n$? $\endgroup$
    – ErroR
    Apr 19, 2022 at 20:58
  • $\begingroup$ @YuvalFilmus Is there a simple argument that show us the lower bound of number of times that we make queries is $\omega(\log n)$? $\endgroup$
    – ErroR
    Apr 19, 2022 at 21:00
  • $\begingroup$ It depends on what you mean by "simple". $\endgroup$ Apr 19, 2022 at 21:01
  • $\begingroup$ @YuvalFilmus If it's complex I have no problem. Also I prefer to give me some hint not full solution. $\endgroup$
    – ErroR
    Apr 19, 2022 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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