This is the 26th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 59th day 🎈!
🚀 Algorithm 🚀

🌲 Maximum number of consecutive 1s

Given a binary array, count the maximum number of consecutive 1s in it.

Example:

Input:1.1.0.1.1.1] output:3Explanation: The first two and the last three are consecutive1, so maximum continuous1The number of is3.
Copy the code

Tip:

  • The input array contains only zeros and ones.
  • The length of the input array is a positive integer and does not exceed 10,000.

🌻C# method: one pass

Code:

public class Solution {
    public int FindMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0, count = 0;
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                count++;
            } else {
                maxCount = Math.Max(maxCount, count);
                count = 0;
            }
        }
        maxCount = Math.Max(maxCount, count);
        returnmaxCount; }}Copy the code

The execution result

By execution time:128Ms, beat out all Java commits79.01% user memory consumption:50.1MB, beat out all Java commits22.22% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1) 
Copy the code

🌻Java method: traversal once

Thinking analytical

  • To get the largest number of consecutive 1’s in the array, you need to traverse the array and record the largest number of consecutive 1’s and the current number of consecutive 1’s.

  • If the current element is 1, the current number of consecutive 1’s is incremented by 1; otherwise, the maximum number of consecutive 1’s is updated with the previous number of consecutive 1’s and the current number of consecutive 1’s is zeroed out.

  • Again after the end of the array, a number of consecutive 1 need to use the current update of the largest continuous 1 number, because the last element of an array of may is 111, and the longest continuous 1 subarray may appear at the end of the array, if again after the end of the array is not update a number of consecutive 1 the largest, will lead to the result error.

Code:

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0, count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                count++;
            } else {
                maxCount = Math.max(maxCount, count);
                count = 0;
            }
        }
        maxCount = Math.max(maxCount, count);
        returnmaxCount; }}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits100.00% user memory consumption:39.5MB, beat out all Java commits89.50% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1) 
Copy the code

💬 summary

  • Today is the fifty-ninth day of the buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!