Maximum length subarray with difference between adjacent elements as either 0 or 1 in C++

We are given an array of any size and the task is to find the subarray of the given array with the elements having difference between adjacent elements as 0 or 1.

Input − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6}

Output − Maximum length subarray with difference between adjacent elements as either 0 or 1 are − 2

Explanation − The adjacent elements in an array with difference as 0 or 1 are {2, 1}, {5, 6}, { 3, 4} and {7.6}. Therefore, the maximum length of subarray is 2.

Input − int arr[] = { 2, 1, 7, 6, 5}

Output − Maximum length subarray with difference between adjacent elements as either 0 or 1 are − 3

Explanation − The adjacent elements in an array with difference as 0 or 1 are {2, 1} and {7, 6, 5}.. Therefore, the maximum length of subarray is 3.

Approach used in the below program is as follows

• Input an array of type integers which can contain positive as well as negative elements.
• Calculate the size of an array and pass an array and size to the function for further functionality.
• Take temporary variable i and set it to 0 and maximum variable and set it to 0.
• Start loop while from i till size of an array.
• Inside the loop, set j to i
• Start another loop which will calculate the subarray with the adjacent elements whether it is 0 or not.
• Inside the loop, increment the value of i.
• Set temp to i-j+1
• Check if maximum is less than temp then set maximum to temp.
• Check whether if j is equals to i then increment the value of i
• Return the maximum
• Print the result.

Example

 Live Demo

#include<bits/stdc++.h> using namespace std; //function to calculate maximum Length subarray with // 0 or 1 difference between adjacent elements int maximum_diff(int arr[], int size){    int i = 0;    int maximum = 0;    while (i < size){       int j = i;       while (i+1 < size && (abs(arr[i] - arr[i + 1]) == 1 || abs(arr[i] - arr[i + 1]) == 0)){          i++;       }       int temp = i - j + 1;       if (maximum < temp){          maximum = temp;       }       if(j == i){          i++;       }    }    return maximum; } int main(){    int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6};    int size = sizeof(arr) / sizeof(arr[0]);    cout<<"Maximum length subarray with difference between adjacent elements as either 0 or 1    are: "<< maximum_diff(arr, size); }

Input

Maximum length subarray with difference between adjacent elements as either 0 or 1 are: 2