Trainsorting – Dynamic Programming

Trainsorting problem appears in uva online judge in which we need to find the longest train length. It can be solved using dynamic programming paradigm.

Uva 11456 – Trainsorting

Erin is an engineer. She drives trains. She also arranges the cars within each train. She prefers to put the cars in decreasing order of weight, with the heaviest car at the front of the train.

Unfortunately, sorting train cars is not easy. One cannot simply pick up a car and place it somewhere else. It is impractical to insert a car within an existing train. A car may only be added to the beginning and end of the train.
Cars arrive at the train station in a predetermined order. When each car arrives, 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.
Given the weights of the cars in the order in which they arrive, what is the longest train that Erin can make?

Input

The first line is the number of test cases to follow. The test cases follow, one after another; the format
of each test case is the following:
The first line contains an integer 0<=n<=2000, the number of cars. Each of the following n lines contains a non-negative integer giving the weight of a car. No two cars have the same weight.

Output

Output a single integer giving the number of cars in the longest train that can be made with the given restrictions.

Explanation

Consider the first train car selected, suppose it is car i. From that single starting point, the train will grow in two independent directions: increasing weight and decreasing weight. Decreasing weights will go in the back and increasing weights in the front. To maximize the overall size of the train, you want to maximize the size of the increasing sequence plus the size of the decreasing sequence. You should therefore calculate this quantity for each possible starting car i and see for which car it is greatest. You subtract 1 when calculating the train size because both the increasing and decreasing sequences share the first car as a starting point, so it gets double-counted if you were to just add lis (i) and lds (i). lis and lds can be solved using dynamic programming easily.

We will calculate lis and lds from the end of an array.

 

Solution :

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std; 

int solve(vector<int> &arr)
{
	vector<int> lis(arr.size(),0);
	vector<int> lds(arr.size(),0);

	lis[0] = 1;
	lds[0] = 1;
	int max = 0;
    for(int i = 1; i < arr.size(); i++)
    {
    	lis[i] = lds[i] = 1;
        for(int j = 0; j  < i ; j++)
        {
        	//int max =
        	if(arr[i] > arr[j] && lis[i] <= lis[j] +1)
        	{
        		lis[i] = lis[j] + 1;
        		//cout<<"lis = "<<lis[i]<<endl;
        	}

        	if(arr[i] < arr[j] && lds[i] <= lds[j] + 1)
        	{
        		lds[i] = lds[j] + 1;
        		//cout<<"lds = "<<lds[i]<<endl;
        	}
        }
    }

    for(int i  =0 ; i < arr.size(); i++)
    {
    	max = std::max(max, lis[i] + lds[i] -1);
    }
    cout<<max<<endl;

}

int main( )
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		if(n>0)
		{
    	vector<int> arr;
	    while(n--)
	    {
	    	int temp;
	    	cin>>temp;
	        arr.push_back(temp);
	        //cout<<temp<<" ";
	    }
	    //! IMPORTANT :  Start from end of an array
	    reverse(arr.begin(), arr.end());
	    	solve(arr);
		}
		else
		{
			cout<<"0"<<endl;
		}
	}
    return 0;
}

Site Footer