ਨਿਰੰਤਰ ਅਰੇ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ MakeMyTrip ਮੋਰਗਨ ਸਟੈਨਲੇ ਪੈਟਮ
ਹੈਸ਼ਿੰਗ ਸਲਾਈਡਿੰਗ ਵਿੰਡੋ

ਦਿੱਤਾ ਇੱਕ ਐਰੇ ਸਿਰਫ 0 ਦੇ ਨੰਬਰ ਅਤੇ 1 ਦੇ ਹੁੰਦੇ ਹਨ. ਸਾਨੂੰ ਸਭ ਤੋਂ ਲੰਬੇ ਅਨੁਕੂਲ ਉਪ-ਐਰੇ ਦੀ ਲੰਬਾਈ ਨੂੰ ਲੱਭਣਾ ਹੈ ਜਿਸ ਵਿੱਚ ਓ ਅਤੇ 1 ਬਰਾਬਰ ਹੁੰਦੇ ਹਨ.

ਉਦਾਹਰਨ

ਇੰਪੁੱਟ

ਅਰਰ = [0,1,0,1,0,0,1]

ਆਉਟਪੁੱਟ

6

ਕਥਾ

ਸਭ ਤੋਂ ਲੰਬਾ ਅਨੁਕੂਲ ਉਪ-ਐਰੇ ਲਾਲ ਵਿੱਚ ਨਿਸ਼ਾਨਬੱਧ ਕੀਤਾ ਗਿਆ ਹੈ [0,1,0,1,0,0,1] ਅਤੇ ਇਸ ਦੀ ਲੰਬਾਈ 6 ਹੈ.

ਐਲਗੋਰਿਥਮ

  1. ਮੈਕਸਲੇਨ ਦਾ ਮੁੱਲ 0 ਦਿਓ.
  2. ਪਹਿਲੇ ਲੂਪ ਸੈੱਟ ਵਿਚ ਜ਼ੀਰੋ_ਕਾਉਂਟ ਨੂੰ 0, ਵਨ_ਕਾਉਂਟ ਤੋਂ 0.
  3. ਜੇ ਮੁੱਲ ਦਾ ਇੱਕ ਖਾਸ ਸੂਚਕਾਂਕ ਤੇ ਐਰੇ 0 ਦਾ ਪਾਇਆ ਤਾਂ ਜ਼ੀਰੋ_ਕਾਉਂਟ ਨੂੰ 1 ਨਾਲ ਵਧਾਓ.
  4. ਹੋਰ ਅਪਡੇਟ ਕਰੋ ਅਤੇ 1_ ਦੁਆਰਾ ਇੱਕ_ਗਣਨਾ ਨੂੰ ਵਧਾਓ.
  5. ਹਰੇਕ ਦੁਹਰਾਓ ਤੇ ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਜ਼ੀਰੋ_ਕਾਉਂਟ ਇਕ_ਕਾਉਂਟ ਦੇ ਬਰਾਬਰ ਹੈ, ਜੇ ਬਰਾਬਰ ਹੈ, ਤਦ ਵੱਡਾ ਨੰਬਰ ਲੱਭੋ (ਮੈਕਸਲੇਨ ਅਤੇ ਜੇ- i + 1)
  6. ਰਿਟਰਨ ਮੈਕਸਲੇਨ

ਕਥਾ

ਸਾਡਾ ਮੁੱਖ ਵਿਚਾਰ ਸਭ ਤੋਂ ਲੰਬੇ ਸੰਖੇਪ ਉਪਨਗਰੀ ਦੀ ਇੱਕ ਲੰਬਾਈ ਨੂੰ ਲੱਭਣਾ ਹੈ ਜਿਸ ਵਿੱਚ ਜ਼ੀਰੋ ਹੈ ਅਤੇ ਸਿਰਫ ਇੱਕ ਹੈ, ਇਸ ਲਈ ਸਾਡਾ ਮੁੱਖ ਧਿਆਨ ਉਸ ਲੰਬਾਈ ਨੂੰ ਲੱਭਣਾ ਹੈ.

ਇਸ ਲਈ, ਅਸੀਂ ਲੂਪ ਲਈ ਨੇਸਟਡ ਦੀ ਵਰਤੋਂ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ. ਬਾਹਰੀ ਲੂਪ ਵਿਚ, ਅਸੀਂ ਜ਼ੀਰੋ_ਕਾਉਂਟ ਅਤੇ ਇਕ_ਕਾਉਂਟ ਦਾ ਮੁੱਲ 0 ਤੋਂ ਅਰੰਭ ਕਰਦੇ ਹਾਂ, ਕਿਉਂਕਿ ਹਰੇਕ ਦੁਹਰਾਓ ਦੇ ਬਾਅਦ ਜਦੋਂ ਇਹ ਅੰਦਰੂਨੀ ਲੂਪ ਤੋਂ ਬਾਹਰ ਆਉਂਦਾ ਹੈ ਤਾਂ ਸਾਨੂੰ ਇਸ ਨੂੰ ਮੁੜ ਚੈੱਕ ਕਰਨ ਲਈ ਜ਼ੀਰੋ_ਕਾਉਂਟ ਅਤੇ ਇਕ_ਕਾਉਂਟ ਦੇ ਤਾਜ਼ਾ ਮੁੱਲ ਦੀ ਜ਼ਰੂਰਤ ਹੁੰਦੀ ਹੈ. ਜਦੋਂ ਤੱਕ ਐਰੇ ਦੀ ਲੰਬਾਈ ਨਹੀਂ ਹੋ ਜਾਂਦੀ ਅਸੀਂ ਲੂਪ ਉੱਤੇ ਦੁਹਰਾਓਗੇ.

ਹੁਣ ਇਹ ਐਰੇ ਦੇ ਹਰ ਇਕ ਮੁੱਲ ਦੀ ਜਾਂਚ ਕਰਨ ਜਾ ਰਿਹਾ ਹੈ, ਜੇ ਅਰਰ [ਇੰਡੈਕਸ] ਦਾ ਮੁੱਲ 0 ਜਾਂ 1 ਹੈ ਜੇ ਇਸ ਦਾ ਮੁੱਲ 0 ਦੇ ਬਰਾਬਰ ਹੈ ਤਾਂ ਅਪਡੇਟ ਕਰੋ ਅਤੇ ਜ਼ੀਰੋ_ਕਾਉਂਟ ਦੇ ਮੁੱਲ ਨੂੰ 1 ਨਾਲ ਵਧਾਓ ਜਾਂ ਜੇ ਐਰ [ਇੰਡੈਕਸ] ਦਾ ਮੁੱਲ. ਨੂੰ 1 ਹੋਣ ਦੀ ਸੰਭਾਵਨਾ ਹੈ, ਫਿਰ ਇਹ ਅਪਡੇਟ ਹੁੰਦਾ ਹੈ ਅਤੇ 1_ ਦੇ ਨਾਲ XNUMX ਦੀ ਗਿਣਤੀ ਵਧਾਉਂਦਾ ਹੈ.

ਹੁਣ ਅਗਲਾ ਜੇਕਰ ਬਲਾਕ ਇਹ ਵੇਖਣ ਜਾ ਰਿਹਾ ਹੈ ਕਿ ਕੀ ਜ਼ੀਰੋ_ਕਾਉਂਟ ਇਕ_ਕਾਉਂਟ ਦੇ ਬਰਾਬਰ ਹੈ, ਜੇ ਬਰਾਬਰ ਹੈ, ਤਾਂ ਮੈਕਸਲੇਨ ਅਤੇ ਜੇ-ਆਈ +1 ਦੇ ਵਿਚਕਾਰ ਵੱਡੀ ਸੰਖਿਆ ਲੱਭੋ ਅਤੇ ਮੈਕਸਲੇਨ ਵਿਚ ਵੱਡੀ ਸੰਖਿਆ ਨੂੰ ਸਟੋਰ ਕਰੋ.

ਉਦਾਹਰਨ

ਮੰਨ ਲਓ ਐਰੇ ਦਿੱਤੀ ਗਈ ਹੈ: ਐਰ [] = 1,0,0,1,0,1,0 XNUMX}

ਜ਼ੀਰੋ_ਕਾਉਂਟ = 0, ਇਕ_ਕਾਉਂਟ = 0, ਮੈਕਸਲੇਨ = 0

ਆਈ = 0, => ਜੇ = ਆਈ

j = 0

ਐਰ ਤੇ [ਜੇ] 0 ਦੇ ਬਰਾਬਰ ਨਹੀਂ, ਫਿਰ ਇਕ_ਕੌਂਟ ++, ਮਤਲਬ ਇਕ_ਕੌਂਟ = 1

j = 1

ਐਰ [ਜੇ] ਤੇ 0 ਦੇ ਬਰਾਬਰ, ਫਿਰ ਜ਼ੀਰੋ_ਕਾਉਂਟ ++, ਮਤਲਬ ਜ਼ੀਰੋ_ਕਾਉਂਟ = 1

ਇਸ ਜਗ੍ਹਾ ਤੇ ਅਗਲੇ ਜੇ ਬਲਾਕ ਚਲਾਇਆ ਜਾਂਦਾ ਹੈ, ਤਾਂ ਇਹ ਮੈਕਸਲੇਨ ਅਤੇ j-i + 1 ਦੇ ਵਿਚਕਾਰ ਵੱਡਾ ਨੰਬਰ ਦੇਵੇਗਾ ਅਤੇ ਮੈਕਸਲੇਨ ਵਿਚ 2 ਵਾਪਸ ਕਰੇਗਾ.

j = 2

ਐਰ [ਜੇ] ਤੇ 0 ਦੇ ਬਰਾਬਰ, ਫਿਰ ਜ਼ੀਰੋ_ਕਾਉਂਟ ++, ਮਤਲਬ ਜ਼ੀਰੋ_ਕਾਉਂਟ = 2

j = 3

ਐਰ ਤੇ [ਜੇ] 0 ਦੇ ਬਰਾਬਰ ਨਹੀਂ ਹੈ, ਫਿਰ ਇਕ_ਕਾਉਂਟ ++, ਮਤਲਬ ਇਕ_ਕਾਉਂਟ = 2

ਇਸ ਜਗ੍ਹਾ ਤੇ ਅਗਲਾ ਜੇ ਬਲਾਕ ਚਲਾਇਆ ਜਾਂਦਾ ਹੈ, ਇਹ ਮੈਕਸਲੇਨ, ਅਤੇ ਜੇ- i + 1 ਦੇ ਵਿਚਕਾਰ ਵੱਡਾ ਨੰਬਰ ਦਿੰਦਾ ਹੈ ਅਤੇ ਮੈਕਸਲੇਨ ਵਿਚ 4 ਵਾਪਸ ਕਰਦਾ ਹੈ.

j = 4

ਐਰ [ਜੇ] ਤੇ 0 ਦੇ ਬਰਾਬਰ, ਫਿਰ ਜ਼ੀਰੋ_ਕਾਉਂਟ ++, ਮਤਲਬ ਜ਼ੀਰੋ_ਕਾਉਂਟ = 3

j = 5

ਐਰ ਤੇ [ਜੇ] 0 ਦੇ ਬਰਾਬਰ ਨਹੀਂ ਹੈ, ਫਿਰ ਇਕ_ਕਾਉਂਟ ++, ਮਤਲਬ ਇਕ_ਕਾਉਂਟ = 3

ਇਸ ਜਗ੍ਹਾ ਤੇ ਅਗਲਾ ਜੇ ਬਲਾਕ ਚਲਾਇਆ ਜਾਂਦਾ ਹੈ, ਇਹ ਮੈਕਸਲੇਨ, ਅਤੇ ਜੇ- i + 1 ਦੇ ਵਿਚਕਾਰ ਵੱਡਾ ਨੰਬਰ ਦਿੰਦਾ ਹੈ ਅਤੇ ਮੈਕਸਲੇਨ ਵਿਚ 6 ਵਾਪਸ ਕਰਦਾ ਹੈ.

j = 6

ਐਰ [ਜੇ] ਤੇ 0 ਦੇ ਬਰਾਬਰ, ਫਿਰ ਜ਼ੀਰੋ_ਕਾਉਂਟ ++, ਮਤਲਬ ਜ਼ੀਰੋ_ਕਾਉਂਟ = 4

ਅਤੇ ਇਹ ਲੂਪ ਨੂੰ ਦੁਹਰਾਉਂਦਾ ਰਹਿੰਦਾ ਹੈ ਜਦੋਂ ਤੱਕ ਸਾਰੀਆਂ ਸ਼ਰਤਾਂ ਅਸਫਲ ਨਹੀਂ ਹੋ ਜਾਂਦੀਆਂ.

ਅਤੇ ਮੈਕਸਲੇਨ ਨੂੰ 6 ਦੇ ਤੌਰ ਤੇ ਵਾਪਸ ਕਰੋ.

ਲਾਗੂ

ਕੰਟਿuousਸਿੰਗ ਐਰੇ ਲਈ C ++ ਪ੍ਰੋਗਰਾਮ

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}
6

ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ ਕੰਨਟਿਗਿ .ਸ ਐਰੇ ਲਈ

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

ਨਿਰੰਤਰ ਐਰੇ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ * ਐਨ) ਜਿੱਥੇ ਕਿ N ਦਿੱਤੀ ਗਈ ਐਰੇ ਦਾ ਆਕਾਰ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1) ਕਿਉਂਕਿ ਅਸੀਂ ਇਥੇ ਕੋਈ ਵਧੇਰੇ ਥਾਂ ਨਹੀਂ ਵਰਤਦੇ.

ਹਵਾਲਾ