Find the length of the longest increasing subsequence in a given sequence.

increasing-subsequence.cpp

#include <iostream>
using namespace std;

/*
Find the length of the longest increasing subsequence in a given sequence.
A simple array is taken as an example.
Time complexity is linear, O(n)
*/

int main()
{
	int array[] = {1,2,3,4,5,4,3,2,1,0,2,3,4,5,6,7,6,5,7,8};

	int temp = 1, result = 1;
	
	for(int i=0; i < sizeof(array)/4 - 1; i++)
	{
		if(array[i] < array[i+1])
		{
			temp++; 
			if(temp > result)
				result = temp;
		}	
		else
		{
			if(temp > result)
				result = temp;
				
			temp = 1;	
		}
	}
	
	cout<<"Result: "<< result<<endl;

	return 0;
}