fulvioabrahao's blog

Largest continuous sub-array with sum S
By fulvioabrahao, 10 years ago, In English

Hello guys, I'm looking for some algorithm with complexity O(N) to find the largest continuous sub-array of an array V of size N, with sum equal to S. I know there are algorithms with complexity O(NlogN), but I don't know if it's possible with complexity O(N).

Can someone help me?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

We can do this with a hashmap. First, let a_i be the array, and p_i be the prefix sums (i.e. p_i = a_1 + a_2 + ... + a_i). We can compute these prefix sums in O(N) time. Then, for each i, we want to find the smallest j such that p_i — p_j = S. We can use a hashmap to answer this query in constant time. We need p_i = p_j + S, so, as we are iterating through the prefix sums, add into the hashmap an entry with key p_i+S to value i.

Here's some pseudocode to help


// arr is the input array
psum[0] = arr[0];
for (int i = 1; i < N; i++)
  psum[i] = psum[i &mdash; 1] + arr[i];
int maxlength = -1;
for (int i = 0; i < N; i++) {
  if (hashmap.containsKey(psum[i]) {
     int len = i &mdash; hashmap.get(psum[i]) + 1;
     if (len > maxlength) {
       maxlength = len;
     }
  }
  if (!hashmap.containsKey(psum[i]+S)) {
    hashmap.put(psum[i] + S, i);
  }
}
return maxlength;
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it 
    #include <bits/stdc++.h>
using namespace std;

int main() {

    int N, S;
    cin >> N >> S;
    int a[N];
    for(int i = 0; i < N; ++i)
        cin >> a[i];

    int p[N + 1];
    p[0] = 0;
    for(int i = 1; i <= N; ++i)
        p[i] = p[i - 1] + a[i - 1];

    map<int, int> myMap;
    int ans = -1;

    for(int i = 1; i <= N; ++i) {

        if(myMap.find(p[i]) != myMap.end())
            ans = max(ans, i - myMap[p[i]] + 1);

        if(myMap.find(p[i - 1] + S) == myMap.end())
            myMap[p[i - 1] + S] = i;
    }

    cout << ans << endl;

    return 0;
}
    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    hashmap.containsKey could take O(nlogn) time, How would your solution be then O(n) ?

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

What about two pointers?

UPD: Well, it will work only if all numbers are non-negative.

→ Reply
»
10 years ago, # |
  Vote: I like it -28 Vote: I do not like it

You can use this algorithm:

scanf("%d", &n);
ans = -100000000;
for (int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        ans = max (ans, a[i]);
    }
t = 0;
for (int i=1; i<=n; i++)
{
    t += a[i];
    if (t>=0)
    {
        ans = max(ans, t);
    }
    else t = 0;
}
cout << ans;
→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    That's Kadane algorithm, for maximum subarray problem. Not for largest subarray with sum S!

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I knew that but it is too late :v

      → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it -8 Vote: I do not like it

Use a deque and have a variable to keep track of the sum of elements in the deck

insert elements to the back of the deque and add them to the current sum as long as (current sum < S)

As soon as current sum >= S check if current sum = S. If it is, the deque size is the size of a continuous sub-array with sum equal to S. now keep removing elements from the front of the deque till the current sum is < S then continue on

EDIT: while removing elements from the front of the deque you should check if current sum = S everytime

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that works only for input with possitive values.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Lewin's post explains how to solve this problem.

So let's try to solve another problem: find the longest subsequence (not necessarily continuous) with sum S. I don't know fast solution. My only idea is to use polynomials: if we take polynomial (1 + xA[0])(1 + xA[1])... (1 + xA[n - 1]), then coefficient beside xS is a number of subsequences with sum equal to S. But if we modify it a bit, then we can get more information. So we bring in a new variable y. Now the polynomial (1 + xA[0]y)(1 + xA[1]y)... (1 + xA[n - 1]y) is very nice, because coefficient beside xSyk is a number of subsequences with sum equal to S and length equal to k. So we can use some fancy multidimenstional FFT and stuff to get the answer in something like O(Slog2S).

Does anyone know how to solve it better?

→ Reply