Increasing decreasing sequence

#1

please explain the problem of what does it actually require to be printed and on what basis.

#2

hey @dsdishu99 you have to split the given array in max two parts such that the first part should be in strictly decreasing order and second part should be in strictly increasing order.if it is possible to break array in such parts then print true else print false.

#3

how to solve this problem, please explain the logic behind its explanation…!!

#4

@dsdishu99
First we assume that our sequence is decreasing only. We also assume that our sequence is initially valid and only try to disprove it during the course.
We compare our current element with the previous element and based on that comparison make our decision.
If the curr element is equal to the prev element , we see that the sequence is neither strictly increasing or decreasing so we mark our sequence as invalid.
If the curr element is greater than the prev element, then we realise that the sequence has started increasing and we mark it so using a flag variable “goingUp” which we had initially marked as false based on our assumption that the sequence is decreasing.
If the curr element is less than the previous element and the current sequence is also proceeding as decreasing , we are to do nothing. However if the current sequence is increasing and we get a pair for a decreasing sequence then we mark our sequence as invalid since we cannot have a decreasing part after the increasing sequence.
After each iteration , store the value of the curr element into the prev element so that we can compare it with the next input element.

#5

@dsdishu99
Hello,

so basically what we are required to do is check if sequence is decreasing then increasing
we come across 3 types of cases:

  1. entirely increasing
  2. entirely decreasing
  3. decreasing then increasing => all these cases give a true o/p
    all other cases will give a false result

so thought process :
we start iterating until to the position till we have decreasing value
6 3 1
while(i+1 < n and a[i] > a[i+1]){
i++;
}
then we can check for increasing sequence 6 3 1 6 8 9
while(i+1 < n and a[i] < a[i+1])
i++;
then if the array is jumbled up the i points to some intermediate position,
if after 1 iteration we end up at the n-1 index ( or incase we do a i++ then we check for i == n ) then true is printed
else we conclude that the array is somewhat jumbled up ( increasing decreasing increase pattern or dec inc dec inc) we print false

I have added the code for ur reference

#6

but doesn’t the question ask not to use arrays or lists…!

#7

@dsdishu99
You can solve this problem without storing the data into an array. As you can see , the comparisons are always with the previous element. So evaluate your final answer while taking the input. Take the input in a variable , say current.
cin >> current ;
Then compare it with the previous value. Previous value is the last input you had obtained.
Run the conditions as mentioned by the TA’s in above responses and make your final decision based on that. After evaluating , update your prev variable to current variable , since for the next iteration this current element is going to be the previous element.
prev = current ;

Hence we are able to solve this problem without using any extra space and within O(n) time.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#10

Hey @dsdishu99
replied u here Increasing decreasing sequence