   Type like pro

# Increasing array subsequence

## Problem

You are given an integer array. Find all the subsequences of the array which has the elements in increasing order. B is a subsequence of array A if B can be formed by removing some elements from the array A without disturbing the order of elements. For example {2,5,6,1,3} is the input array, Then {2,5}, {2,6}, {2,6,1}, {2,1,3} are some of its subsequences. In these {2,5}, {2,6} are increasing subsequences.

## Solution

We will use memoization to solve this problem. At any index i of the given array we will have a subproblem of finding all the increasing subsequences till the index i. Then we will check with i+1th element. Some of these subsequences maintain the increasing property after adding this element. we will add this i+1th element to those subsequences and add the number itself as a single element subsequence to the previously memoized solution. As this i+1th element can itself be starting of another sequence. The complexity of the algorithm is output sensitive as we have to find all possible outputs. Let there be k number of increasing subsequences possible. Then the complexity is O(n*k). The term k is the total possible subsequeces. Which is of the order of 2^n. So in upper bound term it is O(n*2^n). But this complexity will only arises when all the subsequences are increasing subsequences. That occurs when the given array is sorted increasingly. In a random array the value of k is supposed to be much less than 2^n.

## Code

```import java.util.ArrayList;

public class IncreasingArraySubsequence
{

/**
* create subsequence of a given array where every
* element in the subsequence is greater than its
* previous element
*
* @param args
*/
public static void main(String[] args)
{
int[] input =
{ 2, 5, 6, 1, 3 };
int length = input.length;
ArrayList < ArrayList < Integer > > table =
new ArrayList < ArrayList < Integer > >();

for (int i = 0; i < length; ++i)
{
ArrayList < ArrayList < Integer > > tempTable =
new ArrayList < ArrayList < Integer > >();
for (ArrayList < Integer > j : table)
{
if (j.get(j.size() - 1) <= input[i])
{
ArrayList < integer > temp = new ArrayList < integer >();
}
}
ArrayList < Integer > temp =
new ArrayList < Integer >();
}

// output
for (ArrayList < Integer > i : table)
{
for (Integer j : i)
{
System.out.print(j + ", ");
}
System.out.println();
}
}

}

```