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[i-1] + 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!
