leetcode解题: Max Consecutive Ones (485)

发表于 | 分类于

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

1
2
3
4
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.

Note:

The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000

解法1：O(N),一次遍历

dp的思想，dp[i] = dp[i - 1] + 1 if dp[i] == 1 else dp[i] = 0, 然后用一个res来记录当前遇到的最大值即可。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int res = 0;
        
        for (int num: nums) {
            if (num == 1) {
                ++count;
                res = Math.max(res, count);
            } else {
                count = 0;
            }
        }
        return res;
    }
}