Longest Bitonic Subarray - C++ Solution

1. Introduction

The Longest Bitonic Subarray problem is a fascinating question in the realm of array processing. It involves finding a contiguous subarray where the elements first increase and then decrease, forming a bitonic sequence. The challenge lies in identifying the longest such subarray in a given sequence of integers.

Problem

Given an integer array, the task is to find the longest bitonic subarray. A bitonic subarray is one where elements first increase, reach a peak, and then decrease. The solution should find the longest such subarray and can return any one of them if multiple subarrays of maximum length exist.

2. Solution Steps

1. Use two arrays, inc and dec, of the same size as the input array. inc[i] stores the length of the increasing subarray ending at i, and dec[i] stores the length of the decreasing subarray starting at i.

2. Traverse the array from left to right to fill the inc array and from right to left to fill the dec array.

3. The length of the longest bitonic subarray ending at i is inc[i] + dec[i] - 1.

4. Find the maximum of these lengths to get the length of the longest bitonic subarray.

5. Extract the subarray from the original array using this information.

3. Code Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find the longest bitonic subarray
vector<int> findLongestBitonicSubarray(vector<int>& nums) {
    int n = nums.size();
    vector<int> inc(n, 1), dec(n, 1);

    // Fill inc[] from left to right
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i - 1]) {
            inc[i] = inc[i - 1] + 1;
        }
    }

    // Fill dec[] from right to left
    for (int i = n - 2; i >= 0; i--) {
        if (nums[i] > nums[i + 1]) {
            dec[i] = dec[i + 1] + 1;
        }
    }

    // Find the length of the longest bitonic subarray
    int maxLength = 1, start = 0;
    for (int i = 0; i < n; i++) {
        if (maxLength < inc[i] + dec[i] - 1) {
            maxLength = inc[i] + dec[i] - 1;
            start = i - inc[i] + 1;
        }
    }

    return vector<int>(nums.begin() + start, nums.begin() + start + maxLength);
}

int main() {
    vector<int> nums = {3, 5, 8, 4, 5, 9, 10, 8, 5, 3, 4};
    vector<int> result = findLongestBitonicSubarray(nums);

    // Print the result
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

4 5 9 10 8 5 3

Explanation:

The program finds the longest bitonic subarray by first calculating the lengths of the longest increasing and decreasing subarrays ending and starting at each index. 

It then determines the maximum length of a bitonic subarray by combining these lengths. The longest bitonic subarray is then extracted from the original array. 

This approach efficiently finds the longest bitonic sequence while ensuring that the subarray adheres to the increasing-then-decreasing condition.