Maximum Length Biotonic Subsequence(getting wrong answer)?

#1

import java.util.*;
public class Bitonic {

public static void main(String[] args) {
	// TODO Auto-generated method stub

	Scanner scn = new Scanner(System.in);
	int t = scn.nextInt();
	while(t-->0)
	{
	int n = scn.nextInt();
	
	int arr[]=new int[n];
	for(int i=0;i<n;i++)
	{
		arr[i]=scn.nextInt();
	}
	
	System.out.println(maxlen(arr));
}}

public static int maxlen(int arr[])
{
	int n = arr.length;
	
	int inc[]=new int[n];
	int dec[]=new int[n];
	
	for(int i=0;i<n;i++)
	{
		inc[i]=1;
		dec[i]=1;
	}
	
	for(int i=1;i<n;i++)
	{
		inc[0]=1;
		for(int j=0;j<i;j++)
		{
			if(arr[j]<arr[i])
			{
				inc[i]=Math.max(inc[i], inc[j]+1);
			}
		}
		
	}

// for(int i=0;i<n;i++)
// {
// System.out.print(inc[i]+" ");
//
// }
// System.out.println();
//
int arr1[]=new int[n];
for(int i=0;i<n;i++)
{
arr1[i]=arr[n-1-i];
}

	for(int i=1;i<n;i++)
	{
		dec[0]=1;
		for(int j=0;j<i;j++)
		{
			if(arr1[j]<arr1[i])
			{
				dec[i]=Math.max(dec[i], dec[j]+1);
			}
		}
		
	}	//System.out.println();

// for(int i=0;i<n;i++)
// {
// System.out.print(dec[i]+" ");
//
// }
int max=0;
for(int i=0;i<n;i++)
{
int m=inc[i]+dec[i]-1;
if(max<m)
{
max=m;
}

	}

return max;
}}

#2

What you are thinking is alright. You’re not getting the required results correctly in the inc[ ] and dec[ ]. Try again with the loop calculating the values of these arrays.
Hint: You don’t need a n^2 loop.
And take hint from the Kadane’s Algo too.

1 Like
#3

Sir,not getting it can u provide code.