11456 - Trainsorting

[lbv]

Wouldn't you need to find the LIS and LDS with each car as the starting point?

Usually when you calculate the LIS/LDS of a sequence, you calculate all the partial results in one pass. That is, you calculate the LIS of the range [ 0 : i ] for 0 <= i < n.

Now, your question could also be written as:
(..) find the LIS and LDS with each car as the ending point, in the reversed sequence?

Which, as you can see, is an idea that has been suggested in previous comments, and can be implemented with only one pass. No need to calculate the LIS/LDS n times.

[jddantes]

Right, thanks

[hanguyenqu]

Hepl me. I don't understand why have Runtime error

Code: Select all

#include<stdio.h>

#define MAX 500

int n,arr[MAX],f[MAX],d[MAX];

int LIS(int k)
{
	int i,ma;
	
	if(f[k]!=-1)
		return f[k];
		
	f[k]=1;
	for(i=k+1;i<n;i++){
		if(arr[k]<arr[i]){
			ma=LIS(i)+1;
			if(ma>f[k])
				f[k]=ma;
		}
	}
	return f[k];
}

int LDS(int j)
{
	int i,min;
	
	if(d[j]!=-1){
		return d[j];
	}
	
	d[j]=1;
	for(i=j+1;i<n;i++){
		if(arr[j]>arr[i]){
			min=LDS(i)+1;
			if(min>d[j]){
				d[j]=min;
			}
		}
	}
	return d[j];
}

int main()
{
//	freopen("11456.inp","r",stdin);
	
	int t,it,i,max,li,ld;
	
	scanf("%d",&t);
	
	for(it=0;it<t;it++){
		max=1;
		scanf("%d",&n);
		
		for(i=0;i<n;i++){
			scanf("%d",&arr[i]);
		}
		
		for(i=0;i<n;i++){
			f[i]=-1;
			d[i]=-1;
		}
		
		for(i=0;i<n;i++)
		{
			li=LIS(i);
			ld=LDS(i);
			if(li+ld-1>max){
				max=li+ld-1;
			}
		}
		
		printf("%d\n",max);
	}
	
	return 0;
	
}

[brianfry713]

The first line contains an integer 0 <= n <= 2000, the number of cars.

[jddantes]

AC

[brianfry713]

If n = 0 then print 0