https://www.codechef.com/viewsolution/9712232
This is solution… And not able to get any bugg
Getting right answer for every sample input
someone plzzzz help!!
You should not print anything other than output, So remove printf("enter no of cases ");
ok.i will take care of this now.
Apart frm that d program is ok na?
and thanks for helping
Please edit your answer to make it readable or provide the link to your solution.
why i am gtting tle while submitting .
running well for given test cases
All the test cases turn out fine.
The range of array value is too big to handle for an integer.
You need to use long int in place of int for array values.
My DP solution
What I did was traverse the array from right to left. The rightmost element will always have 1 subarray that is the element itself.
So I call a function to n-1 to 1 to check for every element in the array. If the elements have same sign the subarray at that position will be 1, the number itself. If they are different in sign the number of subarrays at that position will be (1+ no. of subarrays at next position).
Hope it helps.
That’s exactly I also did. This is a good approach
Python coded simple DP solution and very easy to understand as well.
LInk to solution
Just traverse from right to left … and if sign of current ele is diff than previous then increment 1 on prev count and store this as count of longest alternating subarray for current element …else just put count as 1 for this element.
AC in one go… try this DP approach.
O(n) code
#include
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int arr[n],size[n];
memset(size,0,sizeof(size));
for(int i=0;i<n;i++)
cin>>arr[i];
size[0]=1;int posi=0;
int tot=1;
for(int i=1;i<n;i++)
{
if(arr[i]>0 && arr[i-1]<0 || arr[i]<0 && arr[i-1]>0)
{
tot++;
posi=i-tot+1;
}
else
{
posi=i;
tot=1;
size[i]=tot;
}
size[posi]=tot;
}
for(int i=0;i<n;i++)
{
if(size[i]==0)
{
size[i]=size[i-1]-1;
cout<<size[i]<<" ";
}
else
cout<<size[i]<<" ";
}
cout<<endl;
}
}
Wow such simpler
We can solve this without using dp
keep a variable cnt = 1;
keep a stack or an array to store the values of cnt
Traverse the given array from backwards
cnt variable is updated in every iteration : if a[i] and a[i+1] are alternating then increment cnt , otherwise make cnt = 1 and store the cnt in the stack/array
Now print the stored cnt values…
My solution here