Printing contiguous sub-arrays

Question

The following method of printing all subarrays(contiguous subsequences) of an array is faster as compared to the general method of using three nested for loops:

#include <iostream>
#include <vector>
int main()
{
std::vector<int> array;
int N;
std::cin >> N; //size of array
for (int i = 0; i < N; i++) {
int x;
std::cin >> x;
array.push_back(x);
}
 int i = array.size() - 1;
 std::vector<int> subarray=array;
do {
 std::cout << subarray[array.size()-i-1] << " ";
 if (i == 0) {
 subarray.pop_back();
 if (subarray.empty()) {
 array.pop_back();
 subarray=array;
 }
 std::cout << '\n';
 i = subarray.size() - 1;
 } else {
 i--;
 }
 } while (i >= 0);
}

Can the do while loop be optimized further?

• 200_success: This looks somewhat similar to your previous question, except that it has worse code formatting and lacks some tags. Could you explain why you are seeking an additional review? You already got one comment telling you that cramming more code into one loop is not a good idea.

Answer 1

Your code has one bug that causes it to crash. The line

std::cout << subarray[array.size()-i-1] << " ";

should instead be

std::cout << subarray[subarray.size()-i-1] << " ";

After the first subarray.pop_back(), the subarray access when i == 0 will go past the end of the subarray.

The major flaw of your code is that it does not print all contiguous subarrays. When I input

4
1 2 3 4

Into your program, I get this output:

1 2 3 4
1 2 3
1 2
1
1 2 3
1 2
1
1 2
1
1

Notice that the subarray 2 3 does not appear. Your program is only faster because it does not finish the job. It needs to be able to print subarrays that do not start with the first element of the original array.

You cannot optimize until your program gives the correct output.