Finding the number of longest contiguous increasing subsequences in a given array

Question

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<ll> temp, ll n) 
{ 
    ll count=0,mymax = -1,flag=0,dummy=0;

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

        for (ll i=1; i<n; i++) 
        { 
            if (temp[i] > temp[i-1]) 
                len++; 
            else
            { 
                if (max < len)   
                { 
                    max = len; 
                    maxIndex = i - max; 
                } 
                len = 1;     
            }    
        } 
        if (max < 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;   
}

Answer 1

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:

1. Finding the maximum length: maxLength

   Sequences with next value >= prior value.

2. 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 < prior) {
            if (length > maxLength) {
                maxLength = length;
                maxCount = 1;
            } else if (length == maxLength) {
                ++maxCount;
            }
            length = 0;
            start = false;
        }
        ++length;
        prior = n;
    }
    if (length > maxLength) {
        maxLength = length;
        maxCount = 1;
    } else if (length == maxLength) {
        ++maxCount;
    }
    return maxCount;
}

Complexity O(N).

Answer 2

The code

Before switching to a better algorithm, let's polish the code first. Almost every line of your code can be improved.

1. Get rid of #define ll long long int. This is a standard way to lower the quality of your code. If you mean long long, use long long.

2. Qualify names from the std namespace with std::.

3. Make the parameter temp a const reference (const std::vector<long long>& temp). Copying a vector is expensive.

4. Remove the unnecessary parameter n, which can be calculated with temp.size() if I correctly understand the code.

5. Avoid declaring a bunch of variables at the start of a scope, which makes it hard to follow the logic of the code.

6. Be consistent with your spacing:

   • insert a space after a control keyword, and remove whitespace immediately enclosed by parentheses: if (max < len), not if( max == 1 );

   • insert a space around =: mymax = -1, not count=0;

   • insert a space around binary operators: flag == 0, i < n, temp.begin() + maxIndex + max, not flag==0, i<n, or temp.begin()+maxIndex+max.

7. Remove all trailing whitespaces (whitespace characters at the end of each line).

8. Always use prefix ++ instead of postfix ++ in a discarded-value expression.

9. You are using long long for two different purposes: the value type, and the index type. Use std::size_t or std::vector<long long>::size_type for the second, and templatize the first (or at least make a type alias to it). In fact, restricting yourself to std::vector is not necessary — any container will do.

The algorithm

The better algorithm with \$\operatorname{O}(n)\$ time complexity is described in Joop Eggen's answer — scan the sequence and find the maximum length and count the subsequences simultaneously. Standard algorithms can be of great help here to simplify the code and avoid manual loops. For example, std::is_sorted_until can be used to find contiguous increasing subsequences.

Here's how I'd put the whole thing together:

template <class RandomIt, class Compare = std::less<>>
auto count_longest_sorted_subsequences(RandomIt first, RandomIt last, Compare comp = {})
{
    using Diff = typename std::iterator_traits<RandomIt>::difference_type;
    Diff size{};
    Diff count{};
    for (auto it = first; it != last;) {
        first = std::exchange(it, std::is_sorted_until(first, last, comp));
        if (it - first == size) {
            ++count;
        } else if (it - first > size) {
            size = it - first;
            count = 1;
        }
    }
    return count;
}

Usage example:

std::array arr{2, 7, 1, 8, 2, 8, 1, 8, 2, 8};
assert(count_longest_sorted_subsequences(arr.begin(), arr.end()) == 5);

Answer 3

• Don't use #define ll long long int and don't use long long int either. Use auto for values and size_t for indices and cardinalities.

• Your method should take iterators as parameters. It will still work with vectors, but also with linked lists and other containers.

• Have a well defined behaviour for corner cases, such as empty lists. This behaviour should be documented in a comment.

• Don't use indices and index calculations if not neccessary. There are container types that don't support indexing.

• Dont't erase or otherwise modify the container or its contents if not neccessary or expected by the caller.

• This particular problem can be solved by iterating over the list just once (see code below).

I would have written it like this:

template <class ForwardIterator>
size_t count_longest_sorted_subsequences (ForwardIterator first, ForwardIterator last)
{
    // The empty list contains no subsequences. If you want a different behavior,
    // such as one subsequence of zero length, modify these two lines.
    size_t maxlength = 0;
    size_t maxcount = 0;
    auto next = first;
    while (next != last)
    {
        // Move the 'next'-iterator until a decreasing element is discovered.
        // Count the number of moves (also works for non-random access iterators).
        size_t length = 1;
        auto prev = next++;
        while (next != last && *prev <= *next)
        {
            length++;
            prev = next++;
        }
        // Adjust 'maxlength' and 'maxcount'
        if (length == maxlength)
        {
            maxcount++;
        }
        else if (length > maxlength)
        {
            maxlength = length;
            maxcount = 1;
        }
    }
    return maxcount;
}

Answer 4

For the algorithm, it can be shortened by only checking if a sub-sequence qualifies when it is finished.

using ll = long long;

int LongestSubSeq(const std::vector<ll>& arr)
{
    int numSeq = 0;
    int longest = 0;
    int length = 0;
    size_t size = arr.size();
    for(size_t i = 1; i < size; ++i)
    {
        ++length;
        if(arr[i] <= arr[i-1])
        {
            if(length > longest)
            {
                longest = length;
                numSeq = 1;
            }        
            else if(length == longest)
            {
                ++numSeq;
            }
            length = 0;
        }


    }
    return numSeq;
}