Write a Program to find the longest positive sequence in array.For eg-> Input -> 1 2 -4 6 7 8 9 -5 3 Output -> 6 7 8 9

Answer 1

Hehe, it is quiet easy once you understand whats going on.
I'm just gonna assume you don't know anything about this.

part 1:
std::vector<int> v;
First I declare a vector, which is a dynamic array, and from now I will call it dynamic array, so I can take any amount of input as long as I have available memory.
<int> is a template in this case this dynamic array will hold ints

int N;
std::cin >> N;
Next I ask for the number the user will enter, lets say the user enters 6

while(N--)
{
int input;
std::cin >> input;
v.push_back(input);
}

The while loop goes from 6 -> 5 -> 4 -> 3 -> 2 -> 1 and when it hits 0 it breaks because 0 is false.
Every iteration it gets new input and adds this to the dynamic array.

for(const auto& i : some_array_like_structure)
std::cout << i << " ";

This is an enhanced for loop, just like
It iterates through the array,
const means its content will never change
auto means I let the compiler decide what type it should be,
the & means take everything by reference so I avoid copying everything.

Now inside the function
findLongestSequence<int>(v.begin(), v.end()) that is called instead of some_array_like_structure

template<typename T, typename RandomAccessIter>
I use templates because they are not bound to a specific data type.
So they could take a dynamic array with ints, strings, or any other user defined data type.
T and RandomAccessIter are simply replaced by the compiler by the correct type
in this case T fails to automatically get deduced by the compiler so I have to specify it by adding <int> after the function call.

RandomAccessIter does get automatically deduced in this case so I don't have to specify that one.

typedef typename std::iterator_traits<RandomAccessIter>::iterator_category iter_category;

There are several types of iterators.
In this case I placed a check to only allow the RandomAccessIter type, and other type will cause a compile error.

Answer 2

I did it the hard way cause I felt like it ^^
https://code.sololearn.com/cPMajjHcLRoT/?ref=app

Answer 3

It was a very easy adjustment, it should work now.
Assuming you consider 0 to be positive, if not just replace 0 by 1 at line 33 and 39

Answer 4

Part 4:
if(f.first.size() > p.first.size())
p.first = f.first;

f.first contains the biggest accepted dynamic array we just found, now we compare it to what we already found.
If the new found array is bigger than the old that means we found a longer sequence and we copy this to p's 1st dynamic array

Now we repeat until the entire array has been checked and we return the longest sequence held by p's first array.

Then we return to
for(const auto& i : findLongestSequence<int>(v.begin(), v.end()))
std::cout << i << " ";

Where it iterates over the result and outputs them to the screen and we are finally done :)

Example:

Assuming the input is:
4
3 -4 5 3

I'll skip to the implementation

1st iteration
begin points to the beginning of the dynamic array
and end points to 1 past the end:

1st iteration:

b e
3 -4 5 3

Initial setup
p.first = (empty)
p.second = 3 -4 5 3

p.second is not empty so we enter the while loop

We call fls function

(These are pointers, when I use * I talk about the number that is being pointed at, without * I talk about the address of the pointer,
you probably need some pointer knowledge to fully get it)

*begin, *begin = 3
It is bigger or equal to 0 so we enter the if statement

We add 3 to r's 1st dynamic array
r.first = 3
r.second = (empty)

Next I make begin points to the next element
b e
3 -4 5 3

Sadly -4 >= 0 is false so we break

r.second becomes the remaining dynamic array
r.first = 3
r.second = -4 5 3

We return from the fls function

f copies whatever r had
p.second then copies whatever f's second dynamic array was so
p.second had 3 -4 5 3
it now becomes -4 5 3

Now it checks if f's 1st dynamic array is bigger than p's 1st dynamic array, in this case p is empty while f has 1 element in it, so f is bigger
and p's 1st copies f's 1st

p's 2nd is not empty yet so we repeat, skipping alot now

*begin is -4 so we go to the else and make it point to the next

Answer 5

Part 3:
VectorPair<T> f = fls<T>(p.second.begin(), p.second.end());
Here I call the actual algorithm

VectorPair<T> r;
I create another pair of dynamic arrays

if(*begin >= 0)
If the first element, 1 in this case is bigger than 0 we enter the if statement
else
begin++;

Otherwise I increment the pointer by 1.
So if it was below 0 it would go to the else statement and increment the pointer by 1
(I'm replacing the original 1 by -1 for this example because it wouldn't trigger with a positive number)
v
-1 4 5 -1 8 9
begin would now point to
v
-1 4 5 -1 8 9
basically ignoring the 1st number

If we did enter the if statement
r.first.push_back(*(begin)++);

Add the number pointed at by begin to r's 1st dynamic array
So r's array looks like:
1st dynamic array: 1
2nd dynamic array: (empty)

for(; begin < end; ++begin)
First check if begin points somwhere inside the dynamic array (because it is possible for it to be incremented so much that it points somewhere outside the array, resulting in undefined behaviour)

if(*begin >= 0)
Same rule here as before, add if the number being pointed at is 0 or more, so this ignores negative numbers as well.
r.first.push_back(*begin);

else
break;
If we encounter any number that didn't match the previous if statement we break outside the loop, note that begin is still pointing to this last invalid number.

r.second = std::vector<T>(begin, end);
Add any number between begin(inc.) and end(excl. again)

return r;
Then we return this

VectorPair<T> f = fls<T>(p.second.begin(), p.second.end());
and copy it to f

p.second = f.second;
The 2nd dynamic array of p then becomes the remaining unchecked dynamic array.

Answer 6

Part 2:
You don't really need to know about this yet but I figured why not ^^
anyway

v.begin() returns an iterator to the beginning of the array
v.end() points to 1 past the array
Assuming that 1 4 5 -1 8 9 are the contents.

So v.begin() points to 1
and v.end() points to an empty spot after 9

return findLongestSequenceImpl<T>(begin, end, iter_category());
Then calls the actual implementation, why not call it directly you ask?
Because it would be a hassle for the user to handle the iter_category himself, this way the user doesn't need to know about it.

So that brings us to this function:
template<typename T, typename RandomAccessIter>
std::vector<T> findLongestSequenceImpl(RandomAccessIter begin, RandomAccessIter end, std::random_access_iterator_tag)

In this function we have this:
VectorPair<T> p;

I have VectorPair<T> defined as:

template<typename T>
using VectorPair = std::pair<std::vector<T>, std::vector<T>>;

This means that whenever I use VectorPair I am actually using std::pair<std::vector<T>, std::vector<T>>, but since it's templated I have to specify the type as well so it becomes VectorPair<T> where T was the already deduced type.

So p has 2 dynamic arrays
p.first, the 1st dynamic array
p.second, the 2nd dynamic array
Currently they are both empty.

p.second = std::vector<T>(begin, end);
Here I initialize the 2nd dynamic array with everything that was between begin and end, end is exclusive.
So now p.second contains: 1 4 5 -1 8 9

while(!p.second.empty())

Here I check if the 2nd dynamic array is not empty, as long as it's not empty I know that we still have some data to check.

Answer 7

Actually I'm a beginner , n ur code is best one but i didn't ask for that .......I asked for a program which can print the longest positive sequence in an arrey
for eg :-
Input : 9 5 -1 4 2 8 -7 8 9 5 3 2 -3 2 1;
Output should be : 8 9 5 3 2 .....bcz it's the longest positive sequence b/w two negative numbers.

Answer 8

oh, from your example I just assumed it had to be +1, srry ^^

Answer 9

ohhh it's ok 😊, n I hope now you will help me 😋

Answer 10

yes,now it works ....but your code is difficult to understand 😑😑

Answer 11

Part 5:
r's 1st = empty
r's 2nd = 5 3

f = r;
p's 2nd becomes f's 2nd
f's 1st is not bigger than p's 1st

p's 5 3 is not empty so we repeat again

again inside fls function:
5 >= 0 is true so we go into the if statement

5 is added to r's 1st
then we point to the next element which is the last 3

3 >= 0 is also true so we add that as well
so r's 1st = 5 3
begin < end now fails so we are done

r's 2nd becomes the remaining array, which is now empty

f = r
p's 2nd = f's 2nd

f's 1st = 5 3
p's 1st = 3

f is bigger than p so we copy
p's 1st = 5 3

p's 2nd is now empty so the while loop stops and we return everythig and now you are finally done :D

Have fun reading all of this :P

Answer 12

Thank you so much Dennis for helping me n also for your valuable time you spend to make me understand your code😄😄😄