## 11456 - Trainsorting

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

### Re: 11456 - Trainsort

jddantes wrote: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
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 11456 - Trainsort

Right, thanks

hanguyenqu
New poster
Posts: 1
Joined: Sun Nov 23, 2014 7:38 am

### Re: 11456 - Trainsorting

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;

}``````
Last edited by brianfry713 on Wed Dec 03, 2014 9:17 pm, edited 1 time in total.
Reason: Added code blocks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11456 - Trainsorting

The first line contains an integer 0 <= n <= 2000, the number of cars.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 11456 - Trainsorting

AC
Last edited by jddantes on Thu Dec 25, 2014 2:23 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11456 - Trainsorting

If n = 0 then print 0
Check input and AC output for thousands of problems on uDebug!