Efficient code in Java please Read the entire input one line at a time and then

Question

Efficient code in Java please

Read the entire input one line at a time and then output a subsequence of the lines that appear in the same order they do in the file and that are also in non-decreasing or non-increasing sorted order. If the file contains n lines, then the length of this subsequence should be at least sqrt(n). For example, if the input contains 9 lines with the numbers 2, 1, 3, 7, 4, 6, 9, 5, 8 then your output should have at least 3 lines, which could be 1,3,4 (increasing) or 2,3,7 (increasing) or 1,4,6,9 (increasing) or 2,6,8 (increasing) or 7,6,5 (decreasing) or ...). Warning/Hint: This is probably the hardest question. You're being asked to implement the Erds–Szekeres theorem

Explanation / Answer

import java.lang.Math;
public class MyClass {
public static void main(String args[]) {
int num[]={10,6,8,12,13,20,40,11,12};
int sub[]=new int[10];
int count=0;
int asc[]=new int[100];
int des[]=new int[100];;
int start=-1;
int i=0,j,k;
int a_d=0;
int root = (int)Math.sqrt(num.length) +1;
  
while(a_d==0)
{
start+=1;
asc[start]=1;
des[start]=1;
for(i=start+1;i<num.length;i++)
{
if(num[i]>num[start])
{
des[i]=0;
for(j=i-1;j>=start;j--)
{
if(num[j]>num[i])
continue;
else if(num[j]<=num[i]&&num[j]>=num[start])
{
asc[i]=asc[j]+1;
break;
}
}
if(asc[i]>=root)
{
a_d = 1; /* we have obtained ascending sequence of length square root of total length*/
break;
}
}
if(num[i]<num[start])
{
asc[i]=0;
for(j=i-1;j>=start;j--)
{
if(num[j]<num[i])
continue;
else if(num[j]>=num[i]&&num[j]<=num[start])
{
des[i]=des[j]+1;
break;
}
}
if(des[i]>=root)
{
a_d = 2; /* we have obtained descending sequence of length square root of total length*/
break;
}
}
if(num[i]==num[start])
{
for(j=i-1;j>=start;j--)
{
if(num[j]==num[i])
{
des[i]=des[j]+1;
asc[i]=asc[j]+1;
break;
}
}
if(des[i]>=root)
{
a_d = 3; /* we have obtained equal sequence of length square root of total length*/
break;
}
}
}
}
if(a_d==1)
{
sub[count++]=num[i];
for(k=i-1;k>=start;k--)
{
if(asc[k]!=0 && asc[k]==asc[i]-1 && num[k]<=num[i])
{
sub[count++]=num[k];
i = k;
}
}
for(i=count-1;i>=0;i--)
System.out.println(sub[i]+" ");
}
else if(a_d==2)
{
sub[count++]=num[i];
for(k=i-1;k>=start;k--)
{
if(des[k]!=0 && des[k]==des[i]-1 && num[k]>=num[i])
{
sub[count++]=num[k];
i = k;
}
}
for(i=count-1;i>=0;i--)
System.out.println(sub[i]+" ");
}
else if(a_d==3)
{
for(k=i;k>=start;k--)
{
if(num[k]==num[start])
System.out.println(num[i]+" ");
}
}
}
}

This program will output your desired result. This program uses dynamic programming approach in which we will proceed taking 1st index as the starting point. At any point of array, we will check if the present number is less than start number or greater than or equal. Please check and ask for any clarification

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.