1.题目介绍

题目地址(485. 最大连续 1 的个数 - 力扣（LeetCode）)

https://leetcode.cn/problems/max-consecutive-ones/

题目描述

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

示例 2:

输入：nums = [1,0,1,1,0,1]
输出：2

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1.

2.题解

2.1 暴力枚举

思路

遍历数组,找到连续次数最多的组合

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int ans = 0, temp = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 1){
                temp++;
            }else{
                ans = max(ans, temp);
                temp = 0;
            }
        }
        ans = max(ans, temp);
        return ans;
    }   
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：\(O(n)\)
• 空间复杂度：\(O(n)\)

2.2 前缀和

思路

记录前缀和,最大的前缀和即为1出现的最大次数

代码

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int n = nums.size();
        vector<int> prev(n);
        for(int i = 0; i < n; i++){
            if(nums[i] == 0) continue;  
            if(i == 0) prev[i] = nums[i];
            else prev[i] = prev[i-1] + nums[i];            
        }
        return *max_element(prev.begin(),prev.end());
    }   
};