# Minimum number of query to find Largest sum of a contiguous subarray

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?

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

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).

• $v^i=A[1..i]$? Or $v^i=A[i]$? Apr 19, 2022 at 21:16
• 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. Apr 19, 2022 at 21:17
• 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}$."? Apr 19, 2022 at 21:18
• That's linear algebra. Apr 19, 2022 at 21:19
• Ooh:) I wasn't passed linear algebra course:). Apr 19, 2022 at 21:20

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$$.

• Upvoted. While Yuval's answer is great, this answer is easily understood. Apr 21, 2022 at 11:50

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].

• Suppose that $n = 3$ and you query $A,A,A+A+A$. Apr 19, 2022 at 20:58
• 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$? Apr 19, 2022 at 20:58
• @YuvalFilmus Is there a simple argument that show us the lower bound of number of times that we make queries is $\omega(\log n)$? Apr 19, 2022 at 21:00
• It depends on what you mean by "simple". Apr 19, 2022 at 21:01
• @YuvalFilmus If it's complex I have no problem. Also I prefer to give me some hint not full solution. Apr 19, 2022 at 21:03