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 >();
     temp.addAll(j);
     temp.add(input[i]);
     tempTable.add(temp);
    }
   }
   table.addAll(tempTable);
   ArrayList < Integer > temp = 
     new ArrayList < Integer >();
   temp.add(input[i]);
   table.add(temp);
  }

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

}

Index