#include <iostream>
#include <utility>

using namespace std;

pair<int,int> findLongestTurbulence(int arr[], int n){
    pair<int,int> ret  = {0,-1};
    int a = -1;
    for(int start = 0; start < n ; start   ){
        a = -1;
        for(int end = start 1; end < n ; end   ){
            if(a == -1){
                if(arr[end] > arr[end-1])
                    a=1;
                else if( arr[end] < arr[end-1])
                    a=0;
                else {
                    // no sequence can be generated starting with start 
                    if(end - start > ret.second - ret.first)
                        ret = {start,start};
                    break;      // CHECK FOR NEXT STARTING POINT
                }
            }
            else if(a == 0){
                if(arr[end] > arr[end-1]){
                    a = 1;
                }
                else{
                    // return this start and end point as this sequence cannot be extended more
                    if(end - start > ret.second - ret.first)
                        ret = { start, end-1};
                    break;
                }
            }
            else{
                if(arr[end] < arr[end-1]){
                    a = 0;
                }
                else{
                    // return this start and end point as this sequence cannot be extended more
                    if(end - start > ret.second - ret.first)
                        ret = { start, end-1};
                    break;
                }
            }
        }
    }
    
    return ret;
}
int main()
{
    int arr[] = {1,8,5,2,6,3,9,7,4,2,3}; // provided sequence 
    int n = sizeof(arr)/sizeof(arr[0]);
    pair<int,int> ans = findLongestTurbulence(arr,n);
    
    for(int i=ans.first;i<ans.second;i  ){
        cout<<arr[i]<<", ";
    }
    cout<<arr[ans.second]<<endl;
}

My assumption was that it is O(n^2) as it has two nested for loops. The goal this code is trying to achieve is to find a longest turbulence in the sequence. ‘Turbulence’ is a consecutive sub-sequence where the numbers rise and drop alternately. Every subsequence of a turbulence is also a turbulence. For example,

• 1 and 8 and 5 are all turbulences because each of them contains only one number.

• 1,8 and 8,5 are both turbulences because 1 rises to 8 in the first sequence and 8 drops to 5 in the second.

• 1,8,5 is a turbulence because 1 rises to 8 and then drops to 5.

• 8,5,2 is not a turbulence because 8 drops twice (first to 5 and then to 2).

• The longest turbulence in the given sequence is 5,2,6,3,9,7 which is also the output.

I think the time complexity of this function is O (n^2) as there are two nested for loops. How would I return the turbulence sequence with a complexity of O(n)?

CodePudding user response：

I admit that your code is too complicated for me. I tried it, but I dont understand it. Anyhow, it can be done with a single loop. To keep it simple I would use two loops (though not nested!). One loop to see if arr[i] < arr[i 1] or arr[i] > arr[i 1].

Also too keep it simple you can exclude the case of arr[i] == arr[i 1] because when the array has subsequent elements that are equal then you can apply the algorithm on sub arrays. A turbulence never contains elements arr[i] == arr[i 1].

To invent some fance name I call it "polarity" 1 when arr[i] > arr[i 1] and -1 when arr[i] < arr[i 1] at even i. At odd indices polarity is reversed (ie -1 when arr[i] > arr[i 1]).

This is what you'll get:

#include <vector>
#include <iostream>
#include <iomanip>

int main()
{
    int arr[] = {1,8,5,2,6,3,9,7,4,2,3};

    std::vector<int> polarity;
    int flip = 1;
    for (size_t i = 0; i < std::size(arr) -1;   i){
        if (arr[i] > arr[i 1]) polarity.push_back(1*flip);
        else polarity.push_back(-1*flip);
        flip *= -1;
    }
    for (size_t i = 0; i< std::size(arr);   i) {
        std::cout << std::setw(5) << arr[i] << " ";
    }
    std::cout << "\n";
    for (size_t i = 0; i < std::size(arr)-1;   i) {
        std::cout << std::setw(5) << polarity[i] << " ";
    }
}

Output:

    1     8     5     2     6     3     9     7     4     2     3 
   -1    -1     1     1     1     1     1    -1     1     1 

I'll leave it to you to find the longest subsequence of equal elements in polarity. In this example it is polarity 1 starting at the element with value 5 till 7 (the last entry with polarity 1 corresponds to elements 9 and 7, thats why 7 is included).