Longest Subarray: CHEFSUB(Assignment)

link: https://www.codechef.com/CU1AP0009/problems/CHEFSUB

You are given an array A of N integers: A1A2, …, AN. You need to find a longest contiguous subarray in the array such that each integer in this subarray is an even integer, and output its length.

A contiguous subarray is of the form AiAi+1, …, Aj, for some i and j.

Input

  • The first line of the input contains an integer T denoting the number of test cases. The description of each test case follows.
  • The first line of each test case contains a single integer N denoting the number of elements in the given array.
  • The second line contains N space-separated integers A1A2, …, AN denoting the array A.

Output

For each test case, output a single line containing the answer.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 105
  • 0 ≤ A1, A2, … , AN ≤ 105

Information to score partial points

  • For 16% of the score, it is guaranteed that N ≤ 100.
  • For further 16% of the score, it is guaranteed that N ≤ 1000.
  • For the rest of the 68% of the score, no extra guarantees. That is, N ≤ 105.

Example

Input:
3
4
1 2 2 4
3
2 4 6
5
2 3 2 2 5

Output:
3
3
2

Explanation

Testcase 1: The longest contiguous subarray that has all its elements even will be the subarray consisting of the 3 elements [2, 2, 4]. Hence, the answer will be 3.

Testcase 2: The longest contiguous subarray that has all its elements even will be the subarray consisting of the 3 elements [2, 4, 6]. Hence, the answer will be 3.

Testcase 3: The longest contiguous subarray that has all its elements even will be the subarray consisting of the 2 elements [2, 2]. Hence, the answer will be 2.

Solution:

#include <bits/stdc++.h>
using namespace std;

bool is_even(int a)
{
    if (a % 2 == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }

        // sort(a, a + n);
        int count = 0;
        int ans = -1 ;

        for (int i = 0; i < n; i++)
        {
            /* code */
            if (is_even(a[i]) )
            {
                count++;
                ans = max(count ,ans);
            }
            else{
                count = 0;
            }
        }

        cout << ans << endl;
    }

    return 0;
}

* The material and content uploaded on this website are for general information and reference purposes only. Please do it by your own first. COPYING MATERIALS IS STRICTLY PROHIBITED.


More from PROGIEZ