# problem code - ALTARAY(dynamic programming)

Can anyone please tell why we have to use two loops if we check by looping from i=0 to i=n-1 and why not if we start looping from backwards
basically why complexity is n square by looping from start and why complexity reduces to n if we loop from backwards

//HERE IS MY CODE

``````#include<bits/stdc++.h>
using namespace std;

int main()
{
int test;
scanf("%d",&test);
while(test--)
{
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
int dp[n];
dp[0]=1;
if(arr[0]*arr[1]<0)
dp[1]=2;
else
dp[1]=1;
for(int i=0;i<n-1;i++)
{
if(arr[i]*arr[i+1]<0)
dp[i+1]=dp[i]+1;
else
dp[i+1]=1;
}
int maxy=-1;
for(int f=0;f<n;f++)
if(dp[f]>maxy)
maxy=dp[f];
printf("%d\n",maxy);
}
return 0;
}``````

Because in dp transition for calculating the value of dp[i] we need the value of dp[i+1] first transition would be dp[i] = 1 if a[i+1] is same sign as a[i] else value would be dp[i+1] + 1. This question has to be solved looping backwards if you loop forward you would calculate the value of longest suffix that is longest alternating subarray that ends at x