increase Decrease Max Subsequence

increase Decrease Max Subsequence

  December 31, 2017    

---

Problem:

 x1 < x2 > x3 < x4 > x5 < …. xn or 

  x1 > x2 < x3 > x4 < x5 > …. xn 

Find max subsequence of this pattern(either possible)


Use two index 0 for 1st case and 1 for 2nd


Code:
import java.util.*;
import java.lang.*;
import java.io.*;
class increaseDecreaseMaxSubsequence
 {
public static int increaseDecreaseMaxSubsequence(int arr[],int n)
{
int dp[][]=new int[n][2];
int res=1;
for(int i=0;i<n;++i)
Arrays.fill(dp[i],1);
for(int i=1;i<n;++i)
for(int j=0;j<i;++j)
{
if(arr[i]>arr[j])
dp[i][0]=Math.max(dp[i][0],dp[j][1]+1);
if(arr[i]<arr[j])
dp[i][1]=Math.max(dp[i][1],dp[j][0]+1);
res=Math.max(res,Math.max(dp[i][0],dp[i][1]));
}
return res;
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(increaseDecreaseMaxSubsequence(arr,n));
}
}
}