Максималды тізбекті шешімдер


Күрделілік дәрежесі оңай
Жиі кіреді Amazon
Array

Проблемалық мәлімдеме

Максималды дәйектілік проблемасында екілік массив берілген. Берілген массивте кезектесетіндердің максималды санын табуымыз керек.
Кіріс массивінде тек 0 және 1 болады.

мысал

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

Түсіндіру:
Алғашқы екі цифр немесе соңғы үш цифр қатарынан 1 сандарын құрайды.
Тізбектелген 1-дің максималды саны - 3.

[0,1,0]
1

Түсіндіру:
Тізбектелген 1-дің максималды саны - 1.

жақындау

Бұл мәселені шешу үшін массивтегі индекстерді екіге бөліп қайталай аламыз цикл кезінде кірістірілген келесі алгоритм бойынша:

1. Айнымалы максимумды жасаңыз, ол жүру кезінде жаңартылған максималды 1-ді сақтайды.
2. Бірінші индексі бар i айнымалысын құрыңыз және инициалдаңыз.
3. Енді i цифрының өлшеміне дейін while циклін іске қосыңыз.
4. Ілмек ішінде біз ағымдағы i индексіндегі санның 1-не жоқ екенін тексереміз. Егер ол 1-ге тең болмаса, онда жай ғана i индексін көбейтіңіз. Басқа жағдайда, егер ол 1-ге тең болса, онда санау айнымалысын құру арқылы кірістірілген while циклін іске қосыңыз және 0-мен инициализациялаңыз. Содан кейін массивті сол кірістірілген while циклында қатарынан 1s айналдырыңыз. мысалы, [1] 1-ге тең траверсивті массив, төмендегі суретте көрсетілгендей, XNUMX-дегі қатардағы санды көбейте отырып:

Максималды дәйектілік
5. 0 немесе массивтің соңына тап болғаннан кейін, максималды айнымалыны ескі мәнін санау айнымалысында сақталатын ағымдық 1 сандарымен салыстыру арқылы жаңартыңыз.
6. while циклі аяқталғаннан кейін максималды мәнді қайтарады.

Іске асыру

C ++ бағдарламасы ең көп қатарды қолданушыларға арналған Leetcode шешіміне арналған

#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

Максималды тізбектелгендерге арналған Java бағдарламасы

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

Максималды дәйекті адамдар үшін кешенділікті талдау

Уақыттың күрделілігі

O (N): Біз массивтің басталуынан соңғы индексіне дейін өтіп, әр индекске бір рет қана барамыз. Сондықтан уақыттың күрделілігі O (N) сызықтық болады.

Ғарыштың күрделілігі 

O (1): Біз қосымша кеңістікті қолданбаймыз, демек пайдаланылатын орын тұрақты болып табылады.