Description
Given a binary array, find the maximum number of consecutive 1s in this array.
Example 1:
Input: [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.

Naive Solution
Iterating the array, use cnt
to record the number of consecutive ones. Update idx
to the position of next 0
.
The time complexity is： O(N).
class Solution { public: int findMaxConsecutiveOnes(vector<int>& nums) { int ans = 0; int idx = 0; int cnt = 0; while(idx < nums.size()) { if(nums[idx] == 0) idx++; else { cnt = 0; while(idx < nums.size() && nums[idx] == 1) { cnt++; idx++; } ans = max(cnt, ans); } } return ans; } };

Dynamic programming
Define dp(i)
as the length of consecutive 1s ends with position i
. The recurrence relation is:
Time complexity is: O(N), space complexity is: O(N)
class Solution { public: int findMaxConsecutiveOnes(vector<int>& nums) { vector<int> dp(nums.size()); if(nums.size() == 0) return 0; int ans = 0; dp[0] = nums[0] == 1 ? 1 : 0; ans = dp[0]; for(int i=1; i<nums.size(); i++) { if(nums[i] == 1) { dp[i] = dp[i1] + 1; } ans = max(dp[i], ans); } return ans; } };

In this approach we used more memory? Actually, we only need to store the current count of 1s.
If we reduce the array to only a count
, seems we get almost the same code with solution #1.
class Solution { public: int findMaxConsecutiveOnes(vector<int>& nums) { if(nums.size() == 0) return 0; int count = 0; int ans = 0; for(int i=0; i<nums.size(); i++) { if(nums[i] == 1) { count++; } else { ans = max(count, ans); count = 0; } } ans = max(count, ans); return ans; } };

Preparing for an interview? Check out this!