gistfile1.hpp

//#include <cstdio>
#include <string>
#include <vector>
using namespace std;

class IntegerSequence
{
public:
	int maxSubsequence(vector<int> numbers)
	{
		int len = numbers.size();
		int* IncreFn = new int[len];
		int* DecreFn = new int[len];

		for (int i = 0; i < len; i++)
		{
			IncreFn[i] = 1;
			for (int j = 0; j < i; j++)
			{
				if( numbers[j]<numbers[i]   &&  IncreFn[j] + 1 > IncreFn[i]  )
				{
					IncreFn[i] = IncreFn[j] + 1;
				}
			}
		}

		for (int i = len - 1 ; i >= 0; i--)
		{
			DecreFn[i] = 1;
			for (int j = len -1 ; j>i ; j--)
			{
				if ( numbers[j] < numbers[i] && DecreFn[j] +1 > DecreFn[i])
				{
					DecreFn[i] = DecreFn[j] + 1;
				}
			}
		
		}		

		int maxSubLen = 0;
		for (int i = 0 ; i < len ; i ++)
		{
			if (IncreFn[i] + DecreFn[i] >maxSubLen)
				maxSubLen = IncreFn[i] + DecreFn[i];
		}

		return len + 1- maxSubLen;
	}
};