The **longest increasing subsequence problem** looks for numbers, in ascending order, that build the increasing subsequence in an array. To extract the subsequence, the array that stores the integer data is traversed. There will be more than one increasing subsequence, but the sequence with the maximum increasing elements is the one that is displayed as an output. 


# The algorithm
The idea is to use recursion to solve this problem.


1. Find as many subsequences as possible for the current number. 

2. If the current item is greater than the previous element in the subsequence, include the current item in the subsequence and recur for the remaining items. 

3. Exclude the current item from the sequence and recur for the remaining items. 

4. Finally, we return the maximum value that we've gotten by including or excluding the current item. ​


>The base case of ​recursion happens when no items are left.

# Implementation
The following code takes an array and returns the length of the longest increasing subsequence found:

#include <iostream>
#include <climits>
using namespace std;

// Function to find length of longest increasing subsequence
int LIS(int arr[], int i, int n, int prev)
{
	// Base case: if nothing is remaining
	if (i == n)
		return 0;

	// case 1: exclude the current element and process the
	// remaining elements
	int exclude = LIS(arr, i + 1, n, prev);

	// case 2: include the current element if it is greater
	// than previous element in LIS
	int include = 0;
	if (arr[i] > prev)
		include = 1 + LIS(arr, i + 1, n, arr[i]);

	// return maximum of above two choices
	return max(include, exclude);
}

// main function
int main()
{
	int arr[] = { 3, 2, 6, 4, 5, 1 };
	int n = sizeof(arr) / sizeof(arr[0]);

	cout << "Length of the longest increasing subsequence is " 
	<< LIS(arr, 0, n, INT_MIN);

	return 0;
}

class Main
{
	// Function to find length of longest increasing subsequence
	public static int LIS(int[] arr, int i, int n, int prev)
	{
		// Base case: nothing is remaining
		if (i == n) {
			return 0;
		}

		// case 1: exclude the current element and process the
		// remaining elements
		int exclude = LIS(arr, i + 1, n, prev);

		// case 2: include the current element if it is greater
		// than previous element in LIS
		int include = 0;
		if (arr[i] > prev) {
			include = 1 + LIS(arr, i + 1, n, arr[i]);
		}

		// return maximum of above two choices
		return Integer.max(include, exclude);
	}

	// Program for Longest Increasing Subsequence
	public static void main(String[] args)
	{
		int[] arr = { 3, 2, 6, 4, 5, 1 };
		System.out.print("Length of the longest increasing subsequence is " 
		+ LIS(arr, 0, arr.length, Integer.MIN_VALUE));
	}
}

Java

The longest increasing subsequence problem

Finding the longest increasing subsequence in an array involves recursion to include or exclude elements, returning the max sequence length.