I check out that that arrays is bitonic if it first decrease and then decrease then how it possible that {10, 20, 30, 40}, {40, 30, 20, 10}, {10} is also the bitonic arrays these are the extreme example.
Bitobic subarrays example
Hello @Vikaspal,
What is a Biotonic Array?
A subarray A[i … j] is biotonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] … <= A[k] >= A[k + 1] >= … A[j – 1] > = A[j] i.e
- subarray is first increasing and then decreasing or
- entirely increasing or
- entirely decreasing.
So in the question, you have to check for the length of all possible bitonic subarrays and then print the maximum length.
Let’s check if your examples fit the definition I have explained above:
-
{10, 20, 30, 40}
It is entirely increasing.
So, yes it is bitonic. -
{40, 30, 20, 10}
It is entirely decreasing.
So, yes it is bitonic. -
{10}
An array of single element comes under both entirely increasing and entirely decreasing.
So, yes it is bitonic.
Hope, this would help.
Give a like if you are satisfied.
1 Like
I am solving trying to solve like this
First findout out the increasing pattern and then decreasing pattern
a[] = {12,4,78,90,45,23}
In first[] = {4,78,90} then len is 3
in second[] = {90,45,23} then len is 3
as the 90 repeats two time 3+3 -1 and then return the result.
Do u suggest me anything else
I am trying to calculate the decrease arrays len but it gives me the wrong
Hello @Vikaspal,
The approach you have mentioned is good.
You have to do the same for each index of the array.
Reason:
You cannot predetermine at which index you will the maximum length.
This will simplify your efforts
Example:
Let us consider the array {12, 4, 78, 90, 45, 23} to understand the approach.
-
Construct an auxiliary array inc[] from left to right such that inc[i] contains the length of the non-decreaing subarray ending at arr[i].
For A[] = {12, 4, 78, 90, 45, 23}, inc[] is {1, 1, 2, 3, 1, 1} -
Construct another array dec[] from right to left such that dec[i] contains length of non-increasing subarray starting at arr[i].
For A[] = {12, 4, 78, 90, 45, 23}, dec[] is {2, 1, 1, 3, 2, 1}. -
Once we have the inc[] and dec[] arrays, all we need to do is find the maximum value of (inc[i] + dec[i] – 1) at each index.
For {12, 4, 78, 90, 45, 23}, the max value of (inc[i] + dec[i] – 1) is 5 for i = 3.
Hope, this would help.
Give a like if you are satisfied.
can you elborate in my approach where i am failing
Hello @Vikaspal,
In your code, you have to compute the length of increasing and decreasing sequence for each subarray.
- It has greater time complexity.
- Your code doesn’t account for the first increasing then decreasing sequence.
Hope, this will help.
1 Like
@S18ML0016 can u explain this part also
A[i] <= A[i + 1] … <= A[k] >= A[k + 1] >= … A[j – 1] > = A[j] i.e
from The Definition I understood that K is great than or equail to I and the k is less than or equal to J
so in the Above line why <= A[k] >= A[k + 1] > I think that A[k]
is less than A[k+1]
Hello @Vikaspal,
It is for the case when the sequence is first increasing then decreasing.
For that specific case, k will be the index at which the sequence will start decreasing.
For entirely increasing sequence, k will be equal to j
similarly, for entirely decreasing sequence k will be equal to i.
Hope, this might help.
okay got it
I am trying to initialize the array of increasing and decreasing to same value ex: 1 but it not happen
#include
using namespace std;
void maxBitonicLength(int arr[], int n) {
int inc[n]={1}, dec[n]={1};
// Make increasing array
for(int i=0; i<n; i++) {
if(arr[i] < arr[i+1]) {
inc[i+1] = inc[i]+1;
}
}
// Make decreasing arrays
for(int i=n-1; i>=0; i--) {
if(arr[i] < arr[i-1]) {
dec[i-1] = dec[i]+1;
}
}
// Printing the arrays
for(int i=0; i<n; i++) {
cout << inc[i] << " ";
}
cout << endl;
for(int i=0; i<n; i++) {
cout << dec[i] << " ";
}
cout << endl;
// calcualte the index value to find out the maxlength
}
int main() {
int t,n,count=0;
cin >> t;
int arr[1000];
while(count < t) {
cin >> n;
for(int i=0; i<n; i++) {
cin >> arr[i];
}
count++;
maxBitonicLength(arr,n);
}
return 0;
}
Hello @Vikaspal,
-
int inc[n]={1}, dec[n]={1}; statement will set the first element i.e. inc[0] and dec[0] to 1 and every other element gets initialized to zero.
-
as the size of inc and dec is n. So, valid indexes are 0 to n-1.
In your code, you are exceeding this range.
Example:
2.1.
for(int i=0; i<n; i++) {
if(arr[i] < arr[i+1]) {
inc[i+1] = inc[i]+1;
}
}
2.2.
for(int i=n-1; i**>=**0; i–) {
if(arr[i] < arr[i-1]) {
dec[i-1] = dec[i]+1;
}
}
Hope, this would help.
Give a like if you are satisfied.
No I mean to say that Firstly I will initialize all the value to one before comparing to next element if it is greater or less than the elements i will make changes to increasing and decreasing arrays
Let see this code
Hello @S18ML0016,
I have corrected your code:
There are three mistakes.
Refer to the comments for better understanding.
This code will not pass one testcase.
There might be some issue in the testcase.
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.
@S18ML0016 I am doing like this
for(int i=0; i<n; i++) {
if(arr[i] <= arr[i+1]) {
inc[i+1] = inc[i]+1;
}
}
// to make an increasing arrary index
And also I more point if we have equal elements 12 12 so now the index will 1 1 or 1 2 , means we count in increasing or not?
And if in problem statement if given as the constraints like 1<=t<=100 1<=n<=1000000
then I should create a dynamic array or static one a[1000000]
taking two much time N+N+N+N = 4n
