- Arrays, Dynamic Programming, subarray

Longest subarray with all even or all odd elements

Given an array A[ ] of N non-negative integers, the task is to find the length of the longest sub-array such that all the elements in that sub-array are odd or even.Examples:Input: A[] = {2, 5, 7, 2, 4, 6, 8, 3}Output: 4Explanation: Sub-array {2, 4, 6, 8} of length 4 has all even elementsInput: A[] = {2, 3, 2, 5, 7, 3} Output: 3Explanation: Sub-array {5, 7, 3} of length 3 has all odd elements  Naive Approach: A naive approach to solve this problem is to consider all the contiguous sub-arrays and for each sub-array, check if all the elements are even or odd. The longest of them will be the answer.Time Complexity: O(N^2)Auxiliary Space: O(1)Efficient Approach: The main idea to solve this problem is to use Dynamic Programming(it has both the properties – Optimal Substructure and Overlapping Subproblems) such that if there are some contiguous odd elements, then the very next odd element will increase the length of that contiguous array by one. And this is also true for even elements. Follow the steps below to solve the problem: Initialize an array dp[ ] where dp[i] stores the length of sub-array that ends at A[i].Initialize dp[0] with 1.Initialize the variable ans as 1 to store the answer.Iterate over the range [1, N] using the variable i and perform the following steps:If A[i]%2 is equal to A[i-1]%2, then set the value of dp[i] as dp[i-1]+1.Else, set the value of dp[i] as 1.Iterate over the range [0, N] using the variable i and perform the following steps:Set the value of ans as the maximum of ans or dp[i].After performing the above steps, print the value of ans as the answer.Below is the implementation of the above approach:C++#include using namespace std;int LongestOddEvenSubarray(int A[], int N){        int dp[N];        dp[0] = 1;        int ans = 1;        for (int i = 1; i < N; i++) {                        if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0)            || (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) {                        dp[i] = dp[i - 1] + 1;        }        else            dp[i] = 1;    }    for (int i = 0; i < N; i++)                ans = max(ans, dp[i]);        return ans;}int main(){        int A[] = { 2, 5, 7, 2, 4, 6, 8, 3 };    int N = sizeof(A) / sizeof(A[0]);        cout