The problem at first glance seems too straightforward but it's not that much. Think a bit about the lines "Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.". What I understand from these lines is.
1. Erin can choose to start making the train from any point of the arrivals of the cars. So she may have started to make the train from either 1st or n-1st or nth or n/2nd, any point.
2. And from the point in time where she starts this, she checks if the new car is smaller in weight than the last car of her train or higher in weight than the first car or vice versa.
3. So the sorting can start from any point and the optimal choice is at any point.
Ofcourse you have to use LIS, but you also need LDS. Why??
Because suppose she starts from position i. Since she wants to make the train as long as possible so she must make sure the train is optimal from the last till i. Then after i she wants to join the longest possible train using the cars i+1 to n. So, she wants to join the LIS(1 -> i) with LDS(i+1 -> n).
In my solution, I subtracted 1 from LIS(i)+LDS(i) because in both the i car is present. So erased it from 1 of them.
// BISMILLAHIRRAHMANIRRAHIM
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <list>
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>
#define swp(type, a, b) {type x=a; a=b; b=x;}
typedef long long lint;
typedef unsigned long long ulint;
using namespace std;
int seq[10000];
int lis[10000], lds[10000];
int LIS(int n) {
int i, j, mx=0;
for (i=n-1 ; i>=0 ; i--) {
lis[i] = 1;
for (j=i+1 ; j<n ; j++) {
if (seq[i]<seq[j]) {
lis[i] = max(lis[i] , 1+lis[j]);
}
}
mx = max(mx, lis[i]);
}
return mx;
}
int LDS(int n) {
int i, j, mx=0;
for (i=n-1 ; i>=0 ; i--) {
lds[i] = 1;
for (j=i+1 ; j<n ; j++) {
if (seq[i]>seq[j]) {
lds[i] = max(lds[i] , 1+lds[j]);
}
}
mx = max(mx, lds[i]);
}
return mx;
}
int main ( void ) {
int i, kount, kase, n, x, mx, mnn, mxx, len, res;
cin >> kase;
while (kase--) {
cin >> n;
mx = n;
len = 0;
kount = 0;
while (mx--) {
cin >> x;
seq[kount++] = x;
}
LDS(n); LIS(n);
res = 0;
for (i=0 ; i<n ; i++) {
res = max(res, lis[i]+lds[i]-1);
}
/*cout << "{ debug-start" << endl;
for (i=0 ; i<n ; i++) {
cout << seq[i] << " ";
} cout << endl;
for (i=0 ; i<n ; i++) {
cout << lis[i] << " ";
} cout << endl;
for (i=0 ; i<n ; i++) {
cout << lds[i] << " ";
} cout << endl;
cout << "end-debug }" << endl;*/
cout << res << endl;
}
return 0;
}
