Help me in solving ALTARAY problem

help
,
1

My issue

TLE

My code

# cook your dish here
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    dp=[0]*n
    dp[n-1]=1
    for i in range(n-1):
        count=1
        k=i
        while(k<n-1):
            if(a[k]*a[k+1]<0):
                count+=1
            else:
                break
            k+=1
        dp[i]=count
    for i in range(n):
        print(dp[i], end=" ")
    print()

Learning course: Dynamic programming
Problem Link: Alternating subarray prefix Practice Problem in Dynamic programming - CodeChef

2

@ananyeah
your solution if O(n^2).
its won’t work
try to iterate the array from the backward side .
U will get it then.
for reference plzz refer my c++ code

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    long long int a[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
	    int dp[n];
	    dp[n-1]=1;
	    for(int i=n-2;i>=0;i--)
	    {
	        long long int val=a[i]*a[i+1];
	        if(val<0)
	        dp[i]=dp[i+1]+1;
	        else
	        dp[i]=1;
	    }
	    for(int i=0;i<n;i++)
	    cout<<dp[i]<<" ";
	    cout<<endl;
	}
	return 0;
}