Maximum Consecutive Ones

Easy

0/40

Contributed by

75 upvotes

Asked in companies

Problem statement

You are given an array ‘ARR’ of length ‘N’ consisting of only ‘0’s and ‘1’s. Your task is to determine the maximum length of the consecutive number of 1’s.

For Example:

ARR = [0, 1, 1, 0, 0, 1, 1, 1], here you can see the maximum length of consecutive 1’s is 3. Hence the answer is 3.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first input line contains a single integer ‘T’,  representing the number of test cases.

The first line of each test case contains a single integer ‘N’, representing the array's length.

The second line of each test case contains N space-separated integers representing the elements of the array.

Output Format:

For each test case, print a single integer representing the maximum length of consecutive 1’s in the array.

Output for each test case will be printed on a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Sample Input 1:

2
8
0 1 1 0 0 1 1 1
4
0 1 1 0

Sample Output 1:

3
2

Explanation for Sample Output 1:

For the first test case, ‘ARR’ = [0, 1, 1, 0, 0, 1, 1, 1], here you can see the maximum length of consecutive 1’s is 3 when we select ARR[5], ARR[6] and ARR[7]. Hence the answer is 3.

For the second test, ‘ARR’ = [0, 1, 1, 0], here you can see the maximum length of consecutive 1’s is 2 when we select ARR[1] and ARR[2]. Hence the answer is 2.

Sample Input 2:

2
6
1 1 1 1 0 0
4
1 1 1 1

Sample Output 2:

4
4

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 1000
ARR[i] = {0, 1}

Time Limit: 1 sec

Hint 1

Hint 2

Try to iterate over every subarray of the array.

Approaches (2)

Approach 1

Approach 2

Brute Force

Approach:
In this approach, we will iterate over all the possible subarrays of the array starting at each index. If we find an 0 in the subarray we will stop as we have reached the maximum possible consecutive 1’s starting from i'th index, then we will check all the subarrays starting from the next index.

Algorithm:

Iterate’ i’ from 0 to the length of N - 1
- Iterate’ j’ from ‘i’ to the length of N - 1
  - If ‘ARR[j]’ is equal to 0, break this loop
  - Set ‘ans’ as the maximum of itself and j - i + 1
Return ‘ans’

Time Complexity

O( N ^ 2 ), where N is the length of the array

In the worst case, when the array consists of only 1's, we will be generating all the ~(N^2) subarrays.Hence the final time complexity is O(N^2).

Space Complexity

O( 1 )

We are not using any extra space.Hence the overall space complexity is O(1).

(100% EXP penalty)

Maximum Consecutive Ones

Console