Search code examples
c++sub-array

Finding contiguous subarray (without sum)


I want to ask for FAST methods of finding contiguous sub-arrays for a given array. Please note that I am not looking for maximum sum contiguous sub-arrays, rather want to perform other operations on the sub-arrays obtained. I am already aware of the following algorithm, but am looking for more efficient algorithms as this one has a very poor time complexity.

// N = number of elements in array A.
void subarr(int N, int A[]) {
  for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
      for (int k = j; k < N; k++) {
        cout << A[k] << ' ';
      }
      cout << endl;
    }
  }
}

Solution

  • As others have pointed out in comments, your example is incorrect. It should read as something like

    for (int i = 0; i < N; i++) {
       for (int j = N-1; j >= i; j--) {
          for (int k=i; k<=j; k++) {
             cout << "A[" << k << "] ";
         }
         cout << endl;
       }
    }
    

    Note that I changed the output to just printing literally A[k]. This will print every subarray exactly once.

    As for your question, again, as others have pointed out, this algorithm prints each subarray once, without any extra work. I don't believe you can spare runtime as this is almost the least amount of work you have to do. You do have some overhead from the three nested loops, but you probably need all three: a subarray is specified by, for instance,

    1. its starting point
    2. either its end point or its length

    and you have to print/cut out what is in between, giving rise to a third loop.