4
\$\begingroup\$

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;   
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Can you provide a full program, with some test cases? \$\endgroup\$ – L. F. Jan 13 at 10:52
4
\$\begingroup\$

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).

\$\endgroup\$
4
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ OK, you're using algorithms. But you are "doing it twice" compared to Joops code? \$\endgroup\$ – Oliver Schönrock Jan 14 at 8:38
  • 1
    \$\begingroup\$ @OliverSchonrock My mistake. I've updated the answer. \$\endgroup\$ – L. F. Jan 14 at 10:59
3
\$\begingroup\$
  • 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;
}
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Please ... don't use that nasty ll ... \$\endgroup\$ – L. F. Jan 13 at 12:03
  • \$\begingroup\$ It's very common and easy to understand. \$\endgroup\$ – tinstaafl Jan 13 at 12:09
  • \$\begingroup\$ Can you backup your claim? To me, ll is just like tmpl <cls T> cls Arr;, which I don't think will pass the majority of code review :) \$\endgroup\$ – L. F. Jan 13 at 12:14
  • \$\begingroup\$ I should have been more specific in my comment I guess. Since this code is obviously for some sort of challenge/competition, I find that this type of shortcut is very common in those sorts of situations. With common use comes understanding. \$\endgroup\$ – tinstaafl Jan 13 at 12:34
  • 2
    \$\begingroup\$ @mackycheese21 It definitely isn't fine to teach terrible programming practice like #define ll or #include <bits/stdc++.h> on Code Review, a place for readable and production quality code. Remember that Code Review, like every other Stack Exchange site, is designed to benefit the whole community, rather than just OP. \$\endgroup\$ – L. F. Jan 14 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.