Given an array arr of n integers, the task is to find the length of the longest bitonic sequence. A sequence is considered bitonic if it first increases, then decreases. The sequence does not have to be contiguous.
Input: arr = [5, 1, 4, 2, 3, 6, 8, 7]
Output: 6
Explanation: The longest bitonic sequence is [1, 2, 3, 6, 8, 7] with length 6.
Input: arr = [10, 20, 30, 40, 50, 40, 30, 20]
Output: 8
Explanation: The entire array is bitonic, increasing up to 50 and then decreasing.
Input: arr = [12, 11, 10, 15, 18, 1 7, 16, 14]
/*It is pseudocode and it is not tied to
any specific programming language*/
/* Function to return the length of LIS starting from
index i with the element prev_ind element refers to
the previously selected element in the subsequence*/
func(int i, int prev_ind, int arr[]) {
// Not Take case
int notTake = func(i+1, prev_ind, arr);
// Take case
int take = 0;
// If no element is chosen till now
if(prev_ind == -1)
take = func(i+1, i, arr) + 1;
/* Else the current element can be
taken if it is strictly increasing */
else if(arr[i] > arr[prev_ind])
take = func(i+1, i, arr) + 1;
// Return the maximum length obtained from both cases
return max(take, notTake);
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the longest decreasing subsequence
// to the left
int left(int prev, int idx, vector<int>& arr) {
if (idx < 0) {
return 0;
}
// Check if nums[idx] can be included
// in decreasing subsequence
int include = 0;
if (arr[idx] < arr[prev]) {
include = 1 + left(idx, idx - 1, arr);
}
// Return the maximum of including
// or excluding nums[idx]
return max(include, left(prev, idx - 1, arr));
}
// Function to find the longest decreasing
// subsequence to the right
int right(int prev, int idx, vector<int>& arr) {
if (idx >= arr.size()) {
return 0;
}
// Check if nums[idx] can be included
// in decreasing subsequence
int include = 0;
if (arr[idx] < arr[prev]) {
include = 1 + right(idx, idx + 1, arr);
}
// Return the maximum of including or
// excluding nums[idx]
return max(include, right(prev, idx + 1, arr));
}
// Function to find the longest bitonic sequence
int LongestBitonicSequence(vector<int>& arr) {
int maxLength = 0;
// Iterate over potential peaks in the array
for (int i = 1; i < arr.size() - 1; i++) {
// Find the longest decreasing subsequences
// on both sides of arr[i]
int leftLen = left(i, i - 1, arr);
int rightLen = right(i, i + 1, arr);
// Ensure both left and right subsequences are valid
if (leftLen == 0 || rightLen == 0) {
leftLen = 0;
rightLen = 0;
}
// Update maximum bitonic sequence length
maxLength = max(maxLength, leftLen + rightLen + 1);
}
// If no valid bitonic sequence, return 0
return (maxLength < 3) ? 0 : maxLength;
}
};
int main() {
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
// Creating an object of Solution class
Solution sol;
int lengthOfLIS = sol.LIS(nums);
cout << "The length of the LIS for the given array is: " << lengthOfLIS << endl;
return 0;
}
import java.util.*;
class Solution {
// Function to find the longest decreasing subsequence
// to the left
static int left(int prev, int idx, ArrayList<Integer> arr) {
if (idx < 0) {
return 0;
}
// Check if nums[idx] can be included
// in decreasing subsequence
int include = 0;
if (arr.get(idx) < arr.get(prev)) {
include = 1 + left(idx, idx - 1, arr);
}
// Return the maximum of including
// or excluding nums[idx]
return Math.max(include, left(prev, idx - 1, arr));
}
// Function to find the longest decreasing
// subsequence to the right
static int right(int prev, int idx, ArrayList<Integer> arr) {
if (idx >= arr.size()) {
return 0;
}
// Check if nums[idx] can be included
// in decreasing subsequence
int include = 0;
if (arr.get(idx) < arr.get(prev)) {
include = 1 + right(idx, idx + 1, arr);
}
// Return the maximum of including or
// excluding nums[idx]
return Math.max(include, right(prev, idx + 1, arr));
}
// Function to find the longest bitonic sequence
static int LongestBitonicSequence(ArrayList<Integer> arr) {
int maxLength = 0;
// Iterate over potential peaks in the array
for (int i = 1; i < arr.size() - 1; i++) {
// Find the longest decreasing subsequences
// on both sides of nums[i]
int leftLen = left(i, i - 1, arr);
int rightLen = right(i, i + 1, arr);
// Ensure both left and right subsequences are valid
if (leftLen == 0 || rightLen == 0) {
leftLen = 0;
rightLen = 0;
}
// Update maximum bitonic sequence length
maxLength = Math.max(maxLength, leftLen + rightLen + 1);
}
// If no valid bitonic sequence, return 0
return (maxLength < 3) ? 0 : maxLength;
}
}
class Main {
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
// Creating an object of Solution class
Solution sol = new Solution();
int lengthOfLIS = sol.LIS(nums);
System.out.println("The length of the LIS for the given array is: " + lengthOfLIS);
}
}
class Solution:
# Function to find the longest decreasing
# subsequence to the left
def left(prev, idx, arr):
if idx < 0:
return 0
# Check if arr[idx] can be included in the
# decreasing subsequence
include = 0
if arr[idx] < arr[prev]:
include = 1 + left(idx, idx - 1, arr)
# Return the maximum of including or excluding arr[idx]
return max(include, left(prev, idx - 1, arr))
# Function to find the longest decreasing subsequence
# to the right
def right(prev, idx, arr):
if idx >= len(arr):
return 0
# Check if nums[idx] can be included in the
# decreasing subsequence
include = 0
if arr[idx] < arr[prev]:
include = 1 + right(idx, idx + 1, arr)
# Return the maximum of including or excluding arr[idx]
return max(include, right(prev, idx + 1, arr))
# Function to find the longest bitonic sequence
def LongestBitonicSequence(arr):
max_length = 0
# Iterate over potential peaks in the array
for i in range(1, len(arr) - 1):
# Find the longest decreasing subsequences
# on both sides of arr[i]
left_len = left(i, i - 1, arr)
right_len = right(i, i + 1, arr)
# Ensure both left and right subsequences are valid
if left_len == 0 or right_len == 0:
left_len = 0
right_len = 0
# Update maximum bitonic sequence length
max_length = max(max_length, left_len + right_len + 1)
# If no valid bitonic sequence, return 0
return 0 if max_length < 3 else max_length
# Example usage
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# Creating an object of Solution class
sol = Solution()
lengthOfLIS = sol.LIS(nums)
print("The length of the LIS for the given array is:", lengthOfLIS)
var longestStrChain = function(words) {
const chains = new Map(); // Stores the max chain length for each word
const sortedWords = words.slice().sort((a, b) => a.length - b.length); // Sort words by length
for (const word of sortedWords) {
chains.set(word, 1); // Initialize the chain length for the current word
for (let i = 0; i < word.length; i++) {
const pred = word.slice(0, i) + word.slice(i + 1); // Generate predecessor by removing one character
if (chains.has(pred)) {
chains.set(word, Math.max(chains.get(word) || 0, chains.get(pred) + 1));
}
}
}
return Math.max(...Array.from(chains.values())); // Return the maximum chain length
};
// Example usage
let nums = [10, 9, 2, 5, 3, 7, 101, 18];
// Creating an object of Solution class
let sol = new Solution();
let lengthOfLIS = sol.LIS(nums);
console.log("The length of the LIS for the given array is:", lengthOfLIS);
If you draw the recursion tree, you will see that there are overlapping subproblems. Hence the DP approache can be applied to the recursive solution to optimise it.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the longest decreasing subsequence
// to the left
int left(int prev, int idx, vector<int>& arr) {
if (idx < 0) {
return 0;
}
// Check if nums[idx] can be included
// in decreasing subsequence
int include = 0;
if (arr[idx] < arr[prev]) {
include = 1 + left(idx, idx - 1, arr);
}
// Return the maximum of including
// or excluding nums[idx]
return max(include, left(prev, idx - 1, arr));
}
// Function to find the longest decreasing
// subsequence to the right
int right(int prev, int idx, vector<int>& arr) {
if (idx >= arr.size()) {
return 0;
}
// Check if nums[idx] can be included
// in decreasing subsequence
int include = 0;
if (arr[idx] < arr[prev]) {
include = 1 + right(idx, idx + 1, arr);
}
// Return the maximum of including or
// excluding nums[idx]
return max(include, right(prev, idx + 1, arr));
}
// Function to find the longest bitonic sequence
int LongestBitonicSequence(vector<int>& arr) {
int maxLength = 0;
// Iterate over potential peaks in the array
for (int i = 1; i < arr.size() - 1; i++) {
// Find the longest decreasing subsequences
// on both sides of arr[i]
int leftLen = left(i, i - 1, arr);
int rightLen = right(i, i + 1, arr);
// Ensure both left and right subsequences are valid
if (leftLen == 0 || rightLen == 0) {
leftLen = 0;
rightLen = 0;
}
// Update maximum bitonic sequence length
maxLength = max(maxLength, leftLen + rightLen + 1);
}
// If no valid bitonic sequence, return 0
return (maxLength < 3) ? 0 : maxLength;
}
};
int main() {
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
// Creating an object of Solution class
Solution sol;
int lengthOfLIS = sol.LIS(nums);
cout << "The length of the LIS for the given array is: " << lengthOfLIS << endl;
return 0;
}
import java.util.*;
class Solution {
// Function to find the longest decreasing subsequence
// to the left
static int left(int prev, int idx, ArrayList<Integer> arr) {
if (idx < 0) {
return 0;
}
// Check if nums[idx] can be included
// in decreasing subsequence
int include = 0;
if (arr.get(idx) < arr.get(prev)) {
include = 1 + left(idx, idx - 1, arr);
}
// Return the maximum of including
// or excluding nums[idx]
return Math.max(include, left(prev, idx - 1, arr));
}
// Function to find the longest decreasing
// subsequence to the right
static int right(int prev, int idx, ArrayList<Integer> arr) {
if (idx >= arr.size()) {
return 0;
}
// Check if nums[idx] can be included
// in decreasing subsequence
int include = 0;
if (arr.get(idx) < arr.get(prev)) {
include = 1 + right(idx, idx + 1, arr);
}
// Return the maximum of including or
// excluding nums[idx]
return Math.max(include, right(prev, idx + 1, arr));
}
// Function to find the longest bitonic sequence
static int LongestBitonicSequence(ArrayList<Integer> arr) {
int maxLength = 0;
// Iterate over potential peaks in the array
for (int i = 1; i < arr.size() - 1; i++) {
// Find the longest decreasing subsequences
// on both sides of nums[i]
int leftLen = left(i, i - 1, arr);
int rightLen = right(i, i + 1, arr);
// Ensure both left and right subsequences are valid
if (leftLen == 0 || rightLen == 0) {
leftLen = 0;
rightLen = 0;
}
// Update maximum bitonic sequence length
maxLength = Math.max(maxLength, leftLen + rightLen + 1);
}
// If no valid bitonic sequence, return 0
return (maxLength < 3) ? 0 : maxLength;
}
}
class Main {
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
// Creating an object of Solution class
Solution sol = new Solution();
int lengthOfLIS = sol.LIS(nums);
System.out.println("The length of the LIS for the given array is: " + lengthOfLIS);
}
}
class Solution:
# Function to find the longest decreasing
# subsequence to the left
def left(prev, idx, arr):
if idx < 0:
return 0
# Check if arr[idx] can be included in the
# decreasing subsequence
include = 0
if arr[idx] < arr[prev]:
include = 1 + left(idx, idx - 1, arr)
# Return the maximum of including or excluding arr[idx]
return max(include, left(prev, idx - 1, arr))
# Function to find the longest decreasing subsequence
# to the right
def right(prev, idx, arr):
if idx >= len(arr):
return 0
# Check if nums[idx] can be included in the
# decreasing subsequence
include = 0
if arr[idx] < arr[prev]:
include = 1 + right(idx, idx + 1, arr)
# Return the maximum of including or excluding arr[idx]
return max(include, right(prev, idx + 1, arr))
# Function to find the longest bitonic sequence
def LongestBitonicSequence(arr):
max_length = 0
# Iterate over potential peaks in the array
for i in range(1, len(arr) - 1):
# Find the longest decreasing subsequences
# on both sides of arr[i]
left_len = left(i, i - 1, arr)
right_len = right(i, i + 1, arr)
# Ensure both left and right subsequences are valid
if left_len == 0 or right_len == 0:
left_len = 0
right_len = 0
# Update maximum bitonic sequence length
max_length = max(max_length, left_len + right_len + 1)
# If no valid bitonic sequence, return 0
return 0 if max_length < 3 else max_length
# Example usage
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# Creating an object of Solution class
sol = Solution()
lengthOfLIS = sol.LIS(nums)
print("The length of the LIS for the given array is:", lengthOfLIS)
var longestStrChain = function(words) {
const chains = new Map(); // Stores the max chain length for each word
const sortedWords = words.slice().sort((a, b) => a.length - b.length); // Sort words by length
for (const word of sortedWords) {
chains.set(word, 1); // Initialize the chain length for the current word
for (let i = 0; i < word.length; i++) {
const pred = word.slice(0, i) + word.slice(i + 1); // Generate predecessor by removing one character
if (chains.has(pred)) {
chains.set(word, Math.max(chains.get(word) || 0, chains.get(pred) + 1));
}
}
}
return Math.max(...Array.from(chains.values())); // Return the maximum chain length
};
// Example usage
let nums = [10, 9, 2, 5, 3, 7, 101, 18];
// Creating an object of Solution class
let sol = new Solution();
let lengthOfLIS = sol.LIS(nums);
console.log("The length of the LIS for the given array is:", lengthOfLIS);
Q: Find the maximum value of LIS[i] + LDS[i] - 1, since i is counted twice.
A: Compute LIS[i] for every i → The length of the longest increasing subsequence ending at i. Compute LDS[i] for every i → The length of the longest decreasing subsequence starting at i.
Q: Can a strictly increasing or decreasing sequence be considered bitonic?
A: Yes, a purely increasing or purely decreasing sequence is trivially bitonic, with either LIS or LDS contributing fully.
Q: Can this problem be solved using graph-based techniques?
A: Yes! Construct a directed acyclic graph (DAG) where edges exist for increasing and decreasing relationships, then compute the longest path.
Q: How would you modify this problem to allow k fluctuations instead of just one peak?
A: Instead of maintaining a single peak, track alternating increasing and decreasing segments using DP