import java.io.*;
import java.util.*;
import java.lang.*;
class ZigZag
{
public static int longestZigZag(int[] sequence)
{
int i,j,ans=0,l=sequence.length,flag=1,max=0;
int b[]=new int[l-1],dp[]=new int[l-1];
for(i=1;i<l;i++)
{
b[i-1]=sequence[i]-sequence[i-1];
dp[i-1]=1;
}
for(i=1;i<l-1;i++)
{
for(j=0;j<i;j++)
{
if(((b[i]<0&&b[j]>0)||(b[i]>0&&b[j]<0))&&(dp[i]<dp[j]+1))
{
dp[i]=dp[j]+1;
}
}
}
for(i=0;i<l-1;i++)
max=max>dp[i]?max:dp[i];
return max+1;
}
{
int arr[]={1,7,4,9,2,5};
System.
out.
println(longestZigZag
(arr
)); }
}
aW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CgpjbGFzcyBaaWdaYWcKewoJcHVibGljIHN0YXRpYyBpbnQgbG9uZ2VzdFppZ1phZyhpbnRbXSBzZXF1ZW5jZSkKCXsKCQlpbnQgaSxqLGFucz0wLGw9c2VxdWVuY2UubGVuZ3RoLGZsYWc9MSxtYXg9MDsKCQlpbnQgYltdPW5ldyBpbnRbbC0xXSxkcFtdPW5ldyBpbnRbbC0xXTsKCQlmb3IoaT0xO2k8bDtpKyspCgkJewoJCQliW2ktMV09c2VxdWVuY2VbaV0tc2VxdWVuY2VbaS0xXTsKCQkJZHBbaS0xXT0xOwoJCX0KCQlmb3IoaT0xO2k8bC0xO2krKykKCQl7CgkJCWZvcihqPTA7ajxpO2orKykKCQkJewoJCQkJaWYoKChiW2ldPDAmJmJbal0+MCl8fChiW2ldPjAmJmJbal08MCkpJiYoZHBbaV08ZHBbal0rMSkpCgkJCQl7CgkJCQkJZHBbaV09ZHBbal0rMTsKCQkJCX0KCQkJfQoJCX0KCQlmb3IoaT0wO2k8bC0xO2krKykKCQkJbWF4PW1heD5kcFtpXT9tYXg6ZHBbaV07CgkJcmV0dXJuIG1heCsxOwoJfQoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKCQlpbnQgYXJyW109ezEsNyw0LDksMiw1fTsKCQlTeXN0ZW0ub3V0LnByaW50bG4obG9uZ2VzdFppZ1phZyhhcnIpKTsKCX0KfQ==