# Max Consecutive Ones
**Difficulty:** EASY
[External](https://leetcode.com/problems/max-consecutive-ones)
Canonical: https://scaleengineer.com/dsa/problems/max-consecutive-ones
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Deloitte](https://scaleengineer.com/companies/deloitte), [Yandex](https://scaleengineer.com/companies/yandex)
---
## Problem
Given a binary array `nums`, return _the maximum number of consecutive_ `1`_'s in the array_.

**Example 1:**

**Input:** nums = [1,1,0,1,1,1]
**Output:** 3
**Explanation:** The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

**Example 2:**

**Input:** nums = [1,0,1,1,0,1]
**Output:** 2

**Constraints:**

* `1 <= nums.length <= 105`
* `nums[i]` is either `0` or `1`.

# Approaches
## Brute-Force Approach
This approach uses nested loops to check for consecutive ones starting from every possible position in the array. It is straightforward but inefficient.
**Time:** O(n^2), where n is the length of the input array. In the worst-case scenario, such as an array filled with all ones, the inner loop runs up to n times for each of the n elements, resulting in quadratic time complexity. · **Space:** O(1), as we only use a constant amount of extra space for counter variables, regardless of the input array size.
**Pros:** Simple logic that is easy to understand and implement.
**Cons:** Highly inefficient for large inputs due to the O(n^2) time complexity.; Performs redundant work by re-scanning parts of the array multiple times.
### Explanation
The brute-force method involves iterating through each element of the array with an outer loop. For each element, we consider it as a potential starting point of a sequence of ones. Then, a nested inner loop starts from this point and counts how many consecutive ones follow until a zero or the end of the array is encountered.

A variable `maxCount` keeps track of the maximum length found so far. After each inner loop finishes counting a sequence, the count is compared with `maxCount`, and `maxCount` is updated if the new count is larger. This process is repeated for all possible starting positions.

Here is the Java implementation:
```java
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0;
        for (int i = 0; i < nums.length; i++) {
            int currentCount = 0;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] == 1) {
                    currentCount++;
                } else {
                    // End of the current sequence of ones
                    break;
                }
            }
            if (currentCount > maxCount) {
                maxCount = currentCount;
            }
        }
        return maxCount;
    }
}
```
### Algorithm
- Initialize `maxCount = 0`.
- Iterate through the array with an outer loop using index `i` from `0` to `n-1`.
- For each `i`, initialize a `currentCount = 0`.
- Start a nested loop with index `j` from `i` to `n-1`.
- If `nums[j]` is `1`, increment `currentCount`.
- If `nums[j]` is `0`, break the inner loop because the sequence of ones is broken.
- After the inner loop completes, update `maxCount = Math.max(maxCount, currentCount)`.
- After the outer loop finishes, `maxCount` holds the maximum length found.

## Optimal Single Pass Approach
This is an optimal and efficient approach that finds the solution by iterating through the array only once. It maintains a running count of consecutive ones and updates a maximum count whenever a sequence of ones is broken.
**Time:** O(n), where n is the number of elements in the array. This is because we perform a single pass through the array. · **Space:** O(1), as it only requires a couple of integer variables to store the current and maximum counts.
**Pros:** Extremely efficient with a linear time complexity of O(n).; Space-efficient, using only a constant amount of extra memory.; It is the optimal solution since every element must be visited at least once.
**Cons:** There are no significant disadvantages to this approach as it is optimal for this problem.
### Explanation
The single-pass approach is a greedy algorithm that provides an optimal solution. We traverse the array from left to right, keeping track of the length of the current sequence of consecutive ones (`currentCount`). We also maintain a variable `maxCount` to store the maximum length found so far.

As we iterate through the array:
- If we encounter a `1`, we simply increment `currentCount`.
- If we encounter a `0`, it signifies the end of a sequence of ones. We then compare the `currentCount` with `maxCount` and update `maxCount` if the current sequence was longer. After that, we reset `currentCount` to `0`.

One important edge case is when the array ends with a sequence of ones (e.g., `[1, 1, 0, 1, 1, 1]`). The final update to `maxCount` for the trailing sequence happens after the loop concludes.

Here is the Java implementation:
```java
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0;
        int currentCount = 0;
        for (int num : nums) {
            if (num == 1) {
                // Increment the count of consecutive ones
                currentCount++;
            } else {
                // Found a 0, so the sequence is broken
                // Update the max count if the current one is larger
                maxCount = Math.max(maxCount, currentCount);
                // Reset the current count
                currentCount = 0;
            }
        }
        // Final check to account for a sequence at the end of the array
        return Math.max(maxCount, currentCount);
    }
}
```
### Algorithm
- Initialize two integer variables, `maxCount = 0` and `currentCount = 0`.
- Iterate through each `num` in the `nums` array.
- If `num` is `1`, increment `currentCount`.
- If `num` is `0`:
  - The sequence of ones is broken. Update `maxCount = Math.max(maxCount, currentCount)`.
  - Reset `currentCount` to `0`.
- After the loop finishes, there might be a trailing sequence of ones. Perform a final update: `maxCount = Math.max(maxCount, currentCount)`.
- Return `maxCount`.

# Solutions
### Java

```java
class Solution {
public
  int findMaxConsecutiveOnes(int[] nums) {
    int cnt = 0, ans = 0;
    for (int v : nums) {
      if (v == 1) {
        ++cnt;
      } else {
        ans = Math.max(ans, cnt);
        cnt = 0;
      }
    }
    return Math.max(cnt, ans);
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var findMaxConsecutiveOnes =
  function (nums) {
    let res = 0,
      t = 0;
    for (let num of nums) {
      if (num == 1) {
        ++t;
      } else {
        res = Math.max(res, t);
        t = 0;
      }
    }
    return Math.max(res, t);
  };

```

### CPP

```cpp
class Solution {
public:
  int findMaxConsecutiveOnes(vector<int> &nums) {
    int cnt = 0, ans = 0;
    for (int v : nums) {
      if (v == 1) {
        ++cnt;
      } else {
        ans = max(ans, cnt);
        cnt = 0;
      }
    }
    return max(ans, cnt);
  }
};

```

### Python

```python
class Solution:
    # hehe class Solution : def findMaxConsecutiveOnes ( self , nums : List [ int ]) -> int : return max ( len ( s ) for s in '' . join ( str ( x ) for x in nums ). split ( '0' ) )
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int: cnt = ans = 0 for v in nums: if v == 1: cnt += 1 ans = max(ans, cnt) else: cnt = 0 return ans

```