Максимално узастопно решење за Леетцоде


Ниво тешкоће Лако
Често питани у амазонка
Ред

Изјава о проблему

У задатку Мак Цонсецутиве Онес дат је бинарни низ. Морамо пронаћи максималан број узастопних присутних у датом низу.
Улазни низ садржаће само 0 и 1.

Пример

[1,1,0,1,1,1]
3

objašnjenje:
Прве две цифре или последње три цифре узастопне су 1.
Максималан број узастопних 1 је 3.

[0,1,0]
1

objašnjenje:
Максималан број узастопних 1 је 1.

Приступ

Да бисмо решили овај проблем, можемо у два пута поновити индексе у низу угнежђена вхиле петља следећим алгоритмом:

1. Створите променљиву максимум која ће сачувати ажурирани максимум узастопних 1 током преласка.
2. Креирајте и иницијализујте променљиву и са првим индексом.
3. Сада покрените вхиле петљу све док и <величина низа.
4. Унутар петље ћемо проверити да ли је број у тренутном индексу и 1 или није. Ако није једнако 1, једноставно повећајте индекс и. Иначе ако је једнако 1, онда покрените угнежђену вхиле петљу стварањем променљиве бројача и иницијализујте са 0. Затим пређите низ за узастопних 1 у тој угнежђеној петљи вхиле. тј. попречни низ док је нум [и] једнак 1, уз стално повећавање броја тренутних узастопних 1, као што је приказано на доњој слици:

Макс узастопни
5. Након што наиђете на 0 или на крај низа, ажурирајте максималну променљиву упоређујући њену стару вредност са тренутним узастопним бројањем 1 бројева сачуваним у променљивој бројања.
6. Након завршетка петље вратите максималну вредност.

Имплементација

Ц ++ програм за максимално узастопно решење са кодом

#include <bits/stdc++.h>
using namespace std;

int findMaxConsecutiveOnes(vector<int>& nums) {

    int maximum=0;
    int i=0;

    while(i<nums.size())
    {
        int conOnes=0;
        while(i< nums.size() && nums[i]==1)
        {
            conOnes++;
            i++;
        }

        maximum=max(maximum,conOnes);
        i++;
    }

    return maximum; 
}

int main() 
{
    vector<int> nums={1,1,0,1,1,1};
    cout<<findMaxConsecutiveOnes(nums)<<endl;

  return 0; 
}
3

Јава програм за максимално узастопно решење са кодом леетцоде

import java.lang.*;

class MaxOnes
{  
    public static int findMaxConsecutiveOnes(int[] nums) 
    {
        int maximum=0;
        int i=0;

        while(i<nums.length)
        {
        int conOnes=0;
        while(i< nums.length && nums[i]==1)
        {
        conOnes++;
        i++;
        }

        maximum=Math.max(maximum,conOnes);

        i++;
        }

        return maximum; 

    }
    
    public static void main(String args[])
    {
        int nums[]={1,1,0,1,1,1};

        System.out.println(findMaxConsecutiveOnes(nums));
        
    }
}
3

Анализа сложености максималног броја узастопних решења са кодом

Сложеност времена

НА) : Прелазимо низом од почетног до последњег индекса и посећујемо сваки индекс само једном. Стога ће временска сложеност бити линеарна О (Н).

Сложеност простора 

О (1): Не користимо никакав додатни простор, стога је искоришћени простор константан.