Longest Bitonic Sequence in Java
A bitonic sequence is a set of numbers that strictly increases and then decreases periodically. The decreasing portion of a strictly ascending order sequence is empty, and the corresponding bitonic state applies to a strictly descending order sequence. An array which consists of 'n' positive integers is given. The length of the array's longest bitonic subsequence must be determined.
Example 1:
Input:
int a[] = {1, 10, 3, 9, 5, 6, 3, 1};
Output:
The longest bitonic sequence of length is 6.
Explanation:
For the given array, the longest bitonic subsequence (i.e., remove the repeated elements from the array and arrange it in strictly increasing and then strictly decreasing order). Then the list becomes {1, 3, 5, 10, 9, 6}. Hence, the length of the sequence is 6, which is the output.
Example 2:
Input:
int a[] = {1, 1, 2, 1, 3, 4};
Output:
The longest bitonic sequence of length is 4.
Explanation:
For the given array, the longest bitonic subsequence (i.e., remove the repeated elements from the array and arrange it in strictly increasing and then strictly decreasing order). Then the list becomes {1, 2, 3, 4}. Hence, the length of the sequence is 4, which is the output.
Approach: Recursive Method
To determine the length of the longest increasing and decreasing subsequence (bitonic sequence), we can use a recursive method. The key point to consider is that, for every index "i" of an "array," the length of the bitonic sequence that includes index "i" is equal to the sum of the lengths of the longest increasing subsequence that ends at "i" and the longest decreasing subsequence that begins at "i," respectively.
Algorithm:
Step 1: Initialize an array and iterate the entire array.
Step 2: Find the length of the longest increasing sequence which is ending at 'i'.
Step 2.1: Apply recursion on 'increasingSubsequnce'taking parameters as a current index and last element "last."
Step 2.1.1: If ('a[currIndex]' > 'last'), apply a recursive function with a[cur_index].
Step 2.1.2: Else, apply a recursive function without a[cur_index].
Step 3: Find the length of the longest decreasing sequence, which ends at 'i'.
Step 3.1: Apply recursion on 'decreasingSubsequnce'taking parameters as a current index and last element "last."
Step 3.1.1: If ('a[currIndex]' > 'last'), apply a recursive function with a[cur_index].
Step 3.1.2: Else, apply a recursive function without a[cur_index].
Step 4: Therefore, length of longest BitonicSequence at index 'i' == increasingsequence having index 'i' + decreasingsequence having index 'i' - 1.
Step 5: Return the maximum value of the bitonic sequence.
Implementation:
FileName: BitonicRecursive.java
import java.io.*;
import java.util.*;
public class BitonicRecursive
{
public static int BitonicSequence(int[] a, int num)
{
int maxlen = 0;
// iterating the elements of an array
for (int i = 0; i < num; i++)
{
// Considering the longest increasing subsequence prior to index 'i' and
// the longest decreasing subsequence following index 'i,' find the maximum length of a bitonic sequence.
maxlen = Math.max(maxlen, IncreasingSubsequence(a, num, i + 1, 1, 0) + DecreasingSubsequence(a, num, i + 2, i + 1));
}
return maxlen;
}
// A function to determine the longest increasing subsequence's length
public static int IncreasingSubsequence(int[] a, int num, int cur_index, int cur_Len, int last_index)
{
// Base case: if the array's total length is equal to the current index
if (cur_index == num)
{
// Since the last element is a part of the subsequence, if lastIndex = 0, return 1.
// The current element can be included in the subsequence if the last element is greater than the element at lastIndex.
// If this is the case, return 1.
if (last_index == 0 || a[cur_index - 1] > a[last_index - 1])
{
return 1;
}
else
{
// // To indicate an invalid subsequence, return a relatively small number.
return -1000000;
}
}
// Leave out the current index
int ex = IncreasingSubsequence(a, num, cur_index + 1, cur_Len, last_index);
int in = 0;
// Adding the most recent index
// Add the current element to the subsequence if lastIndex is 0
// or if the current element is greater than the element at lastIndex.
if (last_index == 0 || a[cur_index - 1] > a[last_index - 1])
{
in = 1 + IncreasingSubsequence(a, num, cur_index + 1, cur_Len + 1, cur_index);
}
// Return the current element's maximum inclusion and exclusion limits.
return Math.max(in, ex);
}
// The function that determines the length of the longest decreasing subsequence.
public static int DecreasingSubsequence(int[] a, int num, int cur_index, int last_index)
{
// Base case: if the array's total length is greater than the current index
if (cur_index > num)
{
// Return 0 since there are no more elements to include.
return 0;
}
// creating the present index out (excluding index)
int ex = DecreasingSubsequence(a, num, cur_index + 1, last_index);
int in = 0;
// containing the index as of right now
// Add the current element to the subsequence
// if it is smaller than the element at lastIndex.
if (a[cur_index - 1] < a[last_index - 1])
{
in = 1 + DecreasingSubsequence(a, num, cur_index + 1, cur_index);
}
// Return the current element's maximum inclusion and exclusion values.
return Math.max(in, ex);
}
public static void main(String[] args)
{
int[] a = {1, 10, 3, 9, 5, 6, 3, 1};
int num = a.length;
int maxlen = BitonicSequence(a, num);
System.out.println("The longest bitonic sequence of length is " + maxlen);
}
}
Output:
The longest bitonic sequence of length is 7
Complexity Analysis:
The Time Complexity for the above approach is O(n*(2n)), and the Space Complexity is O(n), where n is the number of elements in the array.
Approach: Using Memoization
Memoization is an efficient means of optimizing the recursive method. It eliminates redundancy by saving the results of a single call in a matrix called "memo." This is because multiple recursive calls must be made with the same parameters.
Algorithm:
Step 1: Apply recursive function on parameters 'cur_index' , last index 'last' and a boolean variable 'check'.
Step 2: Call the Recursive function without the inclusion of 'a[cur_index]'.
Step 3: If 'check' == 0, denotes increasing Bitonic Sequence.
Step 3.1: If 'a[cur_index]' > 'a[last]', then include the increasing sequence and apply recursion.
Step 4: If 'check' == 1, it denotes a decreasing Bitonic Sequence.
Step 4.1: If 'a[cur_index]' < 'a[last]', then include the decreasingsequence and apply recursion.
Implementation:
FileName: MemoizationBitonicSequence.java
import java.util.Arrays;
import java.io.*;
public class MemoizationBitonicSequence
{
// // As iterating through the input array's elements, the maxLength function is called for each one, providing as the beginning of a bitonic sequence for that element. It gives back the longest bitonic sequence that was found.
public static int maxLength(int cur_index, int last_index, boolean check, int []a, int [][][]memo, int num)
{
if(cur_index == (num + 1))
{
return 0;
}
// Converting a checkbox to an integer value so that code can utilize it later.
int temp=0;
// The "CHECK" variable is a boolean flag that indicates if the sequence is increasing or decreasing at the moment.
if(check)
{
temp=1;
}
// The memo array is used to store the answers to subproblems to prevent repeating computations,
//reusing the results of previously computed subproblems as necessary enhances the recursive technique.
if(memo[cur_index][last_index][temp] != -1)
{
return memo[cur_index][last_index][temp];
}
// Base condition.
if(last_index == 0)
{
int ex = maxLength(cur_index + 1, last_index, check, a, memo, num);
int in = 1 + maxLength(cur_index + 1, cur_index, check, a, memo, num);
in = Math.max(in, 1 + maxLength(cur_index + 1, cur_index, true, a, memo, num));
return memo[cur_index][last_index][temp] = Math.max(in, ex);
}
if(check)
{
// Exclusion of the current index.
int ex = maxLength(cur_index + 1, last_index, check, a, memo, num);
int in = 0;
// Inclusion of the current index.
if(a[cur_index - 1] < a[last_index - 1])
{
in = 1 + maxLength(cur_index + 1, cur_index, check, a, memo, num);
}
return memo[cur_index][last_index][temp] = Math.max(in, ex);
}
else
{
// Exclusion of the current index.
int ex = maxLength(cur_index + 1, last_index, check, a, memo, num);
int in = 0;
// Inclusion of the current index.
if(a[cur_index - 1] > a[last_index - 1])
{
// After adding the current index, there are two circumstances in which we either stay in the
// increasing portion of the sequence or move to the decreasing part.
in = 1 + maxLength(cur_index + 1, cur_index, check, a, memo, num);
in = Math.max(in, 1 + maxLength(cur_index + 1, cur_index, true, a, memo, num));
}
return memo[cur_index][last_index][temp] = Math.max(in, ex);
}
}
public static int BitonicSequence(int[] a, int num)
{
int ans = 0;
int [][][]memo = new int [num+1][num+1][2];
for(int i=0;i<=num;i++)
{
for(int j=0;j<=num;j++)
{
memo[i][j][0]=-1;
memo[i][j][1]=-1;
}
}
for (int i = 0; i < num; i++)
{
ans = Math.max(ans, maxLength(1, 0, false, a, memo, num));
}
return ans;
}
public static void main(String[] args)
{
int[] a = {1, 10, 3, 9, 5, 6, 3, 1};
int num = a.length;
int maxlen = BitonicSequence(a, num);
System.out.println("The longest bitonic sequence of length is " + maxlen);
}
}
Output:
The longest bitonic sequence of length is 6
Complexity Analysis:
For the above approach, the time complexity is O(N 2), and the Space Complexity is O(N2), where 'n' is the number of elements in the array.
Approach: Using Dynamic Programming
The length of the longest increasing subsequence that ends at index "i" and the longest decreasing subsequence that starts at index "i" can both be found using dynamic programming.
Algorithm:
Step 1: Declare 'list' and 'LDS' that store longest decreasingsequence start at index 'i' and longest increaingsequence end at index 'i'.
Step 2: Calculate "list[i]"
Step 2.1: Iterate through 'j' less than 'i'.
Step 2.2: If a[j] < a[i], update list[i] to max(list[i], list[i] + 1)
Step 3: Calculate "LDS[i]"
Step 3.1: Iterate through 'j' greater than 'i'.
Step 3.2: If a[j] > a[i] update LDS[i] to max(LDS[i], LDS[j] + 1).
Step 4: Calculate the length of the longest BitonicSequence having index 'i' (i.e. (LDS[i] + list[i] - 1)) and return maximum.
Implementation:
FileName: DPBitonicSequence.java
import java.util.Arrays;
import java.io.*;
public class DPBitonicSequence
{
public static int BitonicSequence(int[] a, int num)
{
// The longest increasing sequence's length, terminating at index i, is stored in list[i].
int []list = new int[num];
// The length of the longest decreasing sequence, beginning at index i, is stored in the lds[i].
int []lds = new int[num];
// considers the longest increasing sequence that ends at each index I, calculates its length and stores the result in the list array.
for(int i = 0; i < num; i++)
{
list[i] = 1;
for(int j = 0; j < i; j++)
{
if(a[i] > a[j])
{
list[i] = Math.max(list[i], list[j] + 1);
}
}
}
// starts at each index i, determines the length of the longest decreasing sequence, and puts the result in the lds array.
for(int i = num - 1; i >= 0; i--)
{
lds[i] = 1;
for(int j = i + 1; j < num; j++)
{
if(a[i] > a[j])
{
lds[i] = Math.max(lds[i], lds[j] + 1);
}
}
}
int maxlen = 0;
for(int i = 0; i < num; i++)
{
maxlen = Math.max(maxlen, lds[i] + list[i] - 1);
}
return maxlen;
}
public static void main(String[] args)
{
int[] a = {1, 10, 3, 9, 5, 6, 3, 1};
int num = a.length;
int maxlen = BitonicSequence(a, num);
System.out.println("The longest bitonic sequence of length is " + maxlen);
}
}
Output:
The longest bitonic sequence of length is 6
Complexity Analysis:
The Time Complexity is O(N2) for the dynamic programming approach, and the Space Complexity is O(N), where N represents the number of elements present in the array.