Longest Bitonic Sub-Sequence Problem in C#

Bitonic sub-sequence problem is one of the most frequently asked algorithmic interview questions.
For those who are not sure of what is bitonic sequence, given an array arr[0 … n-1] containing n positive integers, a sequence of arr[] is called Bitonic if it is first increasing, then decreasing.

For example:

{1,2,5,4,3}
{12,16,22,25,10}

Now, what we have to do is find the max length of highest possible bitonic sub-sequence from the given sequence.
Note: The given sequence need not be in bitonic sequence.

Let's take a small example sequence:

{ 9, 10, 3, 1, 2}

Manually, if we try to frame the possible bitonic sub-sequences, you will get:

{9,10,3,1}
{9,10,3,2}
{9,10,1}
{9,10,2}

So the max length of largest bitonic sub-sequence is 4 (i.e., {9,10,3,1} or {9,10,3,2}).

Let's try to solve this with a program (I am using C# here).

A console application with Main function to input the sequence:

static void Main(string[] args)
{
     int max = Bitonic(new int[] { 9, 10, 3, 1, 2 });
     Console.WriteLine(max);
     Console.Read();
}

Now let's see what Bitonic method does:

private static int Bitonic(int[] arr)
{
      // Longest Increasing subsequence
      var lis = GetLIS(arr);

      // Longest Decreasing subsequence 
      var lds = GetLDS(arr);

      Print(arr);
      Print(lis);
      Print(lds);

      // Find the length of maximum length bitonic sequence
      return GetLengthOfMaxLengthBitonicSeq(arr.Length, lis, lds);
}

First, we try to get the longest possible increasing sub-sequence from the input. For this, we will try to give ranking for each element in array. This rank indicates the number of elements from left hand side (from the first element in array) in increasing order to reach the current number including itself.

Let's apply this ranking for the above sequence.

Seq: { 9, 10, 3, 1, 2 }
LIS: { 1, 2, 1, 1, 2 }

Let's have a glance at the source code for GetLIS(arr) method:

private static int[] GetLIS(int[] arr)
{
      int n = arr.Length;
      int[] lis = new int[n];
      for (int i = 0; i < n; i++)
      {
           lis[i] = 1;
           for (int j = 0; j < i; j++)            
                if (arr[i] > arr[j] && lis[i] <= lis[j])
                     lis[i] = lis[j] + 1;
      }
      return lis;
}

Now it's time to get LDS (Longest decreasing sub-sequence). This LDS is also a ranking system, but it is from right hand side. As we know, increasing order from right hand side means decreasing order from left hand side.

Seq: { 9, 10, 3, 1, 2 }
LDS: { 3, 3, 2, 1, 1 }

private static int[] GetLDS(int[] arr)
{
      int n = arr.Length;
      int[] lds = new int[n];
      for (int i = n - 1; i >= 0; i--)
      {
           lds[i] = 1;
           for (int j = n - 1; j > i; j--)
               if (arr[i] > arr[j] && lds[i] <= lds[j])
                    lds[i] = lds[j] + 1;
      }
      return lds;
}

Now it's time to calculate the length of max possible bitonic sub-sequence length by using:

Max of all lis[i]+lds[i]-1 where i is from 0 to n-1

Seq: { 9, 10, 3, 1, 2 }
LIS: { 1, 2, 1, 1, 2 }
LDS: { 3, 3, 2, 1, 1 }

Result: (3+2)-1 = 4

private static int GetLengthOfMaxLengthBitonicSeq(int n, int[] lis, int[] lds)
{
     int max;
     max = lis[0] + lds[0] - 1;
     for (int i = 1; i < n; i++)      
     {           
          if (lis[i] + lds[i] - 1 > max)
          {
               max = lis[i] + lds[i] - 1;
          }
     }
     return max;
}

This is just to print the array:

private static void Print(int[] items)
{
      foreach (var item in items)
      {
           Console.Write(item + ", ");
      }
      Console.WriteLine();
}

Here is the complete working C# code:

using System;

namespace ConsoleApplisation2
{
    class BitonicSubSeq
    {
        static void Main(string[] args)
        {
            int max = Bitonic(new int[] { 9, 10, 1, 3, 5, 8, 2, 1, 7, 5, 3, 1 });
            Console.WriteLine(max);
            Console.Read();
        }

        private static int Bitonic(int[] arr)
        {
            // Longest Increasing subsequence
            var lis = GetLIS(arr);

            // Longest Decreasing subsequence 
            var lds = GetLDS(arr);

            Print(arr);
            Print(lis);
            Print(lds);

            // Find the length of maximum length bitonic sequence
            return GetLengthOfMaxLengthBitonicSeq(arr.Length, lis, lds);
        }

        private static int[] GetLIS(int[] arr)
        {
            int n = arr.Length;
            int[] lis = new int[n];
            for (int i = 0; i < n; i++)
            {
                lis[i] = 1;
                for (int j = 0; j < i; j++)                     
                    if (arr[i] > arr[j] && lis[i] <= lis[j])                         
                         lis[i] = lis[j] + 1;             
            }
            return lis;         
        }         

        private static int[] GetLDS(int[] arr)         
        {             
            int n = arr.Length;             
            int[] lds = new int[n];             
            for (int i = n - 1; i >= 0; i--)
            {
                lds[i] = 1;
                for (int j = n - 1; j > i; j--)
                    if (arr[i] > arr[j] && lds[i] <= lds[j])
                        lds[i] = lds[j] + 1;
            }
            return lds;
        }
        
        private static int GetLengthOfMaxLengthBitonicSeq(int n, int[] lis, int[] lds)
        {
            int max;
            max = lis[0] + lds[0] - 1;
            for (int i = 1; i < n; i++)             
            {                 
                if (lis[i] + lds[i] - 1 > max)
                {
                    max = lis[i] + lds[i] - 1;
                }
            }
            return max;
        }

        private static void Print(int[] items)
        {
            foreach (var item in items)
            {
                Console.Write(item + ", ");
            }
            Console.WriteLine();
        }
    }
}

CodeProject