CODERE3 - Coder Express 3!! - SOLUTION

CODERE3 - Coder Express 3!! is very easy DP problem.

I've solved this problem in O(n^2), but there is a better solution also, which runs in O(n(logn)) time complexity.

This problem is based on longest increasing sub-sequence (link for n*logn recursive DP for LIS).

There are two arrays, l[] and r[]. ith index of l[] tells the longest increasing sub-sequence till ith element, and same is for r[].

For finding longest increasing sub-sequence, we will traverse i 0 to n, and j from i+1 to n, and will check following conditions:

if (a[i] < a[j] && l[j] < l[i] + 1)

                    l[j] = l[i] + 1

And by doing same thing in reverse order, we can get r[].

After calculating l[] and r[], we will find the point where l[i] + r[i] is max. 

This was explanation for O( n^2 ), now try to think solving this problem in   O(n(logn)). 

If you find any difficulty in coding part, refer to the following code: 

	#include "bits/stdc++.h"
	using namespace std;
	typedef unsigned long long ull;
	typedef long long int ll;
	typedef vector<long long int> vi;
	typedef pair<int, int> ii;
	typedef vector<ii> vii;
	int main()
	{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	ll t;
	cin>>t;
	while(t--)
	{
	ll n;
	cin>>n;
	int a[1009];
	int l[1009]={0};
	int r[1009]={0};
	for(int i=0;i<n;i++)
	cin>>a[i];
	for(int i=0;i<n;i++)
	for(int j=i+1;j<n;j++)
	if(a[i]<a[j]&&l[j]<l[i]+1)
	l[j]=l[i]+1;
	for(int i=n-1;i>=0;i--)
	for(int j=i-1;j>=0;j--)
	if(a[i]<a[j]&&r[j]<(r[i]+1))
	r[j]=r[i]+1;
	int maxi=0;
	for(int i=0;i<n;i++)
	{
	if(l[maxi]+r[maxi]<l[i]+r[i])
	maxi=i;
	}
	cout<<l[maxi]+r[maxi]+1<<endl;
	}
	return 0;
	}
	/* freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	*/

view raw CODERE3.cpp hosted with ❤ by GitHub