12
$\begingroup$

We are given an array $a[1 \ldots n]$ with all $a[i]>0$.

Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., $a[j\ldots k]$ for some $j,k$, the sum is the sum of all of the elements of the subarray). For example, if $a=[1,2,1]$, then the answer is 4: we can form $ 1,2,3,4$.

I know how to count the number of distinct sums in $O(n^2)$ time.

Furthermore, I have come to realise this is similar to the classical problem where we need to find the number of distinct substrings of a string. I was thinking of the possibility of constructing a suffix array and solving it in a similar fashion (in $O(n)$ time). But I have not been able to figure out how to modify that to work here. For example, if we use suffix array for $a=[1,2,1]$ we will get 5 cases instead of the four acceptable ones. Is this possible to do this using suffix arrays or am I thinking in the wrong direction?

Also there is one more direction I have been thinking in. Divide and conquer. Like if I divide the array into two parts every time until it is reduced to a single element. A single element can have one sum. Now if we combine two single elements, It can be done in two ways: if both single ranges have same element then we get 2 different sums, or if both have different elements we get 3 different sums. But I am not being able to generalize this for merging arrays of length greater than 1. Is it possible to merge two m size arrays and get the answer in $O(m)$?

$\endgroup$
  • $\begingroup$ Although I don't immediately see how you can derive from it a solution to your problem, the structure of the Maximum Subarray Problem is similar to the problem you describe and has a divide-and-conquer solution which runs in $O(n \ lg \ n)$. $\endgroup$ – Isaac Kleinman Jul 30 '13 at 1:10
  • $\begingroup$ I would suggest starting with the following problem: how hard is it to decide whether there are two intervals with the same sum? It is tempting to prove 3SUM-hardness of this problem, but so far I haven't been able to. $\endgroup$ – Yuval Filmus May 8 '14 at 5:01
2
$\begingroup$

You almost surely can't get better than $O(n^2)$ in the worst case since the number of different sums can be in $\Theta(n^2)$.

Consider e.g. the array $[1,2,4,8,\dotsc, 2^n]$. Here each of the $\frac{n(n+1)}2$ contiguous subarrays has a different sum.


The "almost surely" is due to the fact that the problem does not require the values of the sums as output. However, I don't think duplicates can be avoided without determining at least most of the values.

$\endgroup$
  • $\begingroup$ I see no particular reason why there shouldn't be a way to somehow avoid going over all possibilities while still coming up with the correct answer. Dynamic programming algorithms do that routinely. $\endgroup$ – Yuval Filmus May 8 '14 at 4:48

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.