Finding the number of longest contiguous increasing subsequences in a given array This is different from classic LIS problem. Here I want number of contiguous longest increasing subsequences!

For example:

INPUT: arr[] = { 3, 6, 10, 8, 11, 17, 16, 100 }
OUTPUT: 2


Explanation: There are 2 longest contiguous subsequences: { 3, 6, 10 } and { 8, 11, 17 }.

Here is a function that I have made to achieve the task. But is there any optimized way instead of this brute force approach?

#define ll long long int
ll longestIncSeq(vector&lt;ll&gt; temp, ll n) 
{ 
    ll count=0,mymax = -1,flag=0,dummy=0;

    while( (flag==0) &amp;&amp; (!(temp.empty())) )
    {
        ll max = 1, len = 1, maxIndex = 0; 

        for (ll i=1; i&lt;n; i++) 
        { 
            if (temp[i] &gt; temp[i-1]) 
                len++; 
            else
            { 
                if (max &lt; len)   
                { 
                    max = len; 
                    maxIndex = i - max; 
                } 
                len = 1;     
            }    
        } 
        if (max &lt; len) 
        { 
            max = len; 
            maxIndex = n - max; 
        }    
        if( max == 1 )
        {
            return count;
        }
        if( (mymax == max) || (dummy==0) )
        {
            count++;
            dummy++;
        }
        else
        {
            flag = 1;
        }
        temp.erase(temp.begin()+maxIndex , temp.begin()+maxIndex+max);

        mymax = max;
        n = temp.size();
    }
    return count;   
}
I have no C/C++ compiler at the moment, but the algorithm only needs one loop, the while+flag being a tiny bit too unreadable.

There are two counters:


Finding the maximum length: maxLength

Sequences with next value >= prior value.
Counting the maximum length: maxCount.


length > maxLength reset maxCount to 1
length == maxLength increment maxCount



So (in java):

static int longestIncSeq(int[] arr) {
    int maxCount = 0;
    int maxLength = 0;
    boolean start = true;
    int prior = Integer.MAX_VALUE;
    int length = 0;
    for (int n : arr) {
        if (start || n &lt; prior) {
            if (length &gt; maxLength) {
                maxLength = length;
                maxCount = 1;
            } else if (length == maxLength) {
                ++maxCount;
            }
            length = 0;
            start = false;
        }
        ++length;
        prior = n;
    }
    if (length &gt; maxLength) {
        maxLength = length;
        maxCount = 1;
    } else if (length == maxLength) {
        ++maxCount;
    }
    return maxCount;
}


Complexity O(N).