Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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).
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$.
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].
