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