INCREASING DECREASING SEQUENCE Doubt

#1

Not able to understand the approach even the editorial is not helping. Kindly guide.

#2

it problem based upon bitonic subsequence
A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing. A Bitonic Point is a point in bitonic sequence before which elements are strictly increasing and after which elements are strictly decreasing.
but problem is just opposite of it

1 Like
#3

Abut the approach towards the problem. Since the editorial is not very clear.

#4

Hi Sanket, the approach to this problem is very simple. It is that you take 2 iterators let’s say i & j. Initialize i to 1.
Now iterate over the array until the previous element is greater than it. If you find an element which is greater than it’s previous number then break the loop over there.
After that you put j = i+1 and iterate on the loop again from j = i+1 to n till previous element remains smaller that the current. if you find any element NOW which is smaller than previous
then break the loop again

This is the approach in simplest terms you also have to put some conditions for return: after the first loop ends, after second loop ends which I shall not tell you here because it will be the complete solution then.

Please try the question now.
Hope this helps :slight_smile:

#5

Passed all test cases :100::100:
:wink:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ll n; cin>>n;
	ll start; cin>>start;
	n--;
	ll increase = 0;
	while(n--)
	{
		ll no; cin>>no;
		if((no<start && increase==0) || (no>start && increase==1))
			start = no;
		else if(no>start && increase==0)
		{
			start = no;
			increase =1;
		}
		else
		{
			cout<<"false\n";
			return 0;
		}
	}
	cout<<"true\n";
	// cout<<start;
	return 0;
}