Longest Decreasing Continuous Sequence

[Borab]

Hey. I'm trying to write a program that returns the index of the first number in the longest decreasing continuous sequence in an array but I just can't come up with something that works.

Here's an example

Arr = [5 3 1 4 6 4 3 2]

The longest decreasing continues sequence is 6 4 3 2
And the index of the first number in that sequence is 4
So it will return 4.

Any help would be greatly appreciated.

[vlad from moscow]

#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>

int main()
{
	int a[] = { 5, 3, 1, 4, 6, 4, 3, 2 };

	int *start = a;
	int len = 0;

	for ( int *p = a, *q = a; p != std::end( a ); p = q )
	{
		q = std::adjacent_find( p, std::end( a ), std::less_equal<int>() );
		if ( q != std::end( a ) ) q++;
		int i = std::distance( p, q );
		if ( len < i )
		{
			len = i;
			start = p;
		}
	}

	std::copy_n( start, len, std::ostream_iterator<int>( std::cout, " " ) );
	std::cout << std::endl;
}

EDIT: I forgot include <functional>. Now the code is updated.

[Borab]

Crap, I think I forgot to mention that I'm doing this in C++, I'm a complete tool when it comes to C right now :P

Thanks so much though, I'll figure it out :D

[vlad from moscow]

The code is written in C++.

[cire]

Assuming you can't use stuff from algorithm and that you're probably scratching your head at Vlad's code anway, it is good to begin with a plan. The formulation of this plan often involves sitting down with a pencil and paper and figuring out how you would accomplish the feat that way.

Then, translate it into code.

[Borab]

I'm a beginner and I've been trying to solve this for quite a while with not luck, I wouldn't have come here and asked for help if I hadn't already tried.

Also, I don't understand this code because that's not how I write programs, I never use std and this isn't how I write loops so all that stuff is weird to me.

In the beginning of every program I write I start with

#include <iostream>
using namespace std;

And here's an example of how I write a loop:

for(i=0; i<n; i++)
{
}

Maybe now you understand what I'm trying to say here?

[D80DSL3A]

This exercise is similar to finding the largest value entered by a user.

In that problem you keep two variables, currentValue and maxValue.
You then compare each currentValue with maxValue, replacing maxValue as needed along the way.

The current problem is a bit more involved. You need to track both an index and a value.
I would use these variables:

unsigned int currLength=0, currIndex=0;// for current sequence
unsigned int maxLength=0, maxIndex=0;// for longest sequence 

Then go through the array element by element.
if( A[i+1] < A[i] ) then you are on a decreasing sequence.
This is a new sequence if currLength == 0, in which case you assign currLength = 2 and currIndex = i;
If currLength != 0 then this is a continuing sequence, Just currLength = currLength + 1; this case.

When the test A[i+1] < A[i] fails the sequence (if any) has ended. Compare currLength to maxLength and replace maxIndex, maxLength if needed. Assign currLength = 0 to prepare for the next sequence.

Is this helpful?

[Cubbi]

Borab wrote:

all that stuff is weird to me

It's never too late to learn the basics.

adjacent_find() is the C++ function that searches a sequence (in your case, an array) for the next two adjacent values that satisfy a criterion.

In your case, you're looking for the longest decreasing subsequence, so you need to find the next two adjacent values such that the first is less or equal the second

For example, let's find the end of the decreasing subsequence that begins at the first element:

#include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    int a[] = {5, 3, 1, 4, 6, 4, 3, 2};

    int* p = adjacent_find(begin(a), end(a), less_equal<int>());

    std::cout << "The longest decreasing sequence that starts at position 0 ends at position "
              << distance(a, p) << '\n';
}

online demo: http://liveworkspace.org/code/MzQyOT

(compatibility note: begin() and end() for arrays are fairly new functions in C++, for old compilers, use adjacent_find(a, a+8, less_equal<int>()); or just use vectors, they are better than arrays anyway)

Now, once you have the end of the decreasing sequence that started at position 0, you want to run adjacent_find again to find the end of the sequence that starts at 3 (which is zero-length), and then the sequence that starts at 4 (which goes all the way to the end), and since you're looking for the longest, you'd be recording the new result each time you find a sequence that's longer than the previous. That's what vlad's code does.

[vlad from moscow]

Well, you can investigate the following code

#include <iostream>

using namespace std;

int main()
{
	const int N = 8;
	int a[N] = { 5, 3, 1, 4, 6, 4, 3, 2 };

	int start = 0;
	int len   = 0;

	for ( int i = 0, j = 0; i < N; i = j )
	{
		j = i;

		for ( int k = j; ++j < N && a[j] < a[k]; k++ ) { /* empty body */ }

		if ( len < j - i )
		{
			start = i;
			len = j - i;
		}
	}

	for ( int i = 0; i < len; i++ ) cout << a[start + i] << ' ';
	cout << endl;
}

Don't worry, be happy.:)