15,744,817 members
See more:
I need an efficient algorithm for printing all sub-arrays of an array.
By sub-arrays I mean contiguous subsequences of an array.

What I have tried:

The algorithm available on the web uses three nested for loops with
time complexity O(n^3), which is not at all efficient. Is there a better algorithm which can print all sub-arrays in quadratic or linear time? I l know that time complexity is not determined by the number of loops.
Posted
Updated 15-Jun-22 2:07am
Richard Deeming 15-Jun-22 7:44am
For a single-dimensional array, why would you need more than two loops? (One for the start index, and one for the length.)
Vaibhav Vishal Singh 15-Jun-22 7:50am
I need all sub-arrays (1<=length of sub-array<=length of array)
CPallini 15-Jun-22 8:01am
You forgot the loop needed to print the sequence.

Solution 1

This implements the algorithm suggested by Richard.
Still, it is `O(N^3)`.
C++
```void show_subarrays( int a[], int N)
{
for (int l=1; l<=N; ++l)
{
int k = 0;
while ( (k+l) <= N)
{
for (int j=0; j<l; ++j)
cout << a[k+j] << " ";
cout << "\n";
++k;
}
}
}```

merano99 15-Jun-22 12:00pm
Isnt this a for loop?
int k = 0;
while ( (k+l) <= N) { ... k++;}

for(k=0; (k+l) <= N; k++){..}
CPallini 16-Jun-22 2:52am
Yes, it is.