પુનરાવર્તિત સબબ્રેની મહત્તમ લંબાઈ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ખરેખર કરાત Roblox
અરે દ્વિસંગી શોધ ડાયનેમિક પ્રોગ્રામિંગ હેશિંગ

સમસ્યા "ફરીથી પુનરાવર્તિત સુબ્રrayની મહત્તમ લંબાઈ" માં આપણે બે એરે એરે 1 અને એરે 2 આપ્યા છે, તમારું કાર્ય પેટા-એરેની મહત્તમ લંબાઈ શોધવા માટે છે જે બંનેમાં દેખાય છે એરે.

ઉદાહરણ

ઇનપુટ:

[1,2,3,2,1]
[3,2,1,4,7]

આઉટપુટ:

3

સમજૂતી:

કારણ કે પેટા-એરેની મહત્તમ લંબાઈ 3 છે અને સામાન્ય એરે [3,2,1] છે

પુનરાવર્તિત સબબ્રેની મહત્તમ લંબાઈ

અલ્ગોરિધમ

  1. આઉટપુટ 0 પર સેટ કરો.
  2. વાસ્તવિક ઇનપુટ એરેની લંબાઈ કરતા વધુ 1 લંબાઈવાળા ચલ પૂર્ણાંક એરેને ઘોષણા કરો.
  3. થી શરૂ એરેનું છેલ્લું અનુક્રમણિકા એરે 1 [i] એરે 2 [જે] ની બરાબર છે કે નહીં તે તપાસો, જો સાચું હોય તો વાલ [i] [જે] = વાલ [i + 1] [જે + 1] +1.
  4. આઉટપુટ વાલ કરતા ઓછું છે કે નહીં તે તપાસો [i] [j] પછી આઉટપુટ = વાલ [i] [જે] કરો.
  5. આખા એરે ઉપર તપાસ કરો અને પરિસ્થિતિઓને તપાસો કે અમને મહત્તમ આઉટપુટ મળે છે.
  6. રીટર્ન આઉટપુટ.

સમજૂતી

અમારું આઉટપુટ મેળવવા માટે, આપણે કેટલાક સરળ ટ્રversવર્સિંગ કરવાની જરૂર છે. આ માટે, આપણે આઉટપુટને 0 થી પ્રારંભ કરીશું. પછી આપણે 2-D જાહેર કરીશું મેટ્રિક્સ એરે 1 અને એરે 2 ની લંબાઈ કરતા વધુ લંબાઈ.

આપણે એરેના છેલ્લા ઇન્ડેક્સમાંથી બંને એરેને પસાર કરીશું. તેથી આપણે કેટલીક સ્થિતિઓ ચકાસીશું અને પરિણામ આઉટપુટમાં સંગ્રહિત કરીશું.

તો ચાલો આપણે એક ઉદાહરણ લઈએ અને આગળ વધીએ.

ઉદાહરણ

માની લો કે આની જેમ એરે છે:

પૂર્ણાંક એરે 1 [] = {1,2,3,2,1};

પૂર્ણાંક એરે 2 [] = {3,2,1,4,7};

આઉટપુટ = 0;

  • i = 4, j = 4;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

આઉટપુટ = 0;

  • i = 4, j = 3;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

આઉટપુટ = 0;

  • i = 4, j = 2;

જો એરે 1 [i] == એરે 2 [જે] સાચા અને વ valલ આપે છે [i] [જે] = વાલ [હું + 1] [જે + 1] +1

then val[4][2]=val[5][3]+1=1 then val[i][j]=1.

પછી તપાસો કે આઉટપુટ <વલ [i] [જે] સાચું પાછું આવે છે અને આઉટપુટ = 1 કરે છે.

આઉટપુટ = 1;

  • i = 4, j = 1;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 4, j = 0;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 3, j = 4;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 3, j = 3;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 3, j = 2;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 3, j = 1;

જો એરે 1 [i] == એરે 2 [જે] સાચા અને વ valલ આપે છે [i] [જે] = વાલ [હું + 1] [જે + 1] +1

પછી વાલ [3] [1] = વાલ [4] [2] + 1 = 2 પછી વાલ [3] [1] = 2.

પછી તપાસો કે આઉટપુટ <વલ [i] [જે] સાચું પાછું આવે છે અને આઉટપુટ = વ [લ [i] [જે] કરે છે.

આઉટપુટ = 2;

  • i = 3, j = 0;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 2, j = 4;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 2, j = 3;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 2, j = 2;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 2, j = 1;

જો એરે 1 [i] == એરે 2 [જે] ખોટા વળતર આપે છે અને તે કંઇ કરવા જઇ રહ્યો નથી.

  • i = 2, j = 0;

જો એરે 1 [i] == એરે 2 [જે] સાચા અને વ valલ આપે છે [i] [જે] = વાલ [હું + 1] [જે + 1] +1

પછી વાલ [2] [0] = વાલ [3] [1] + 1 = 2 + 1 પછી વાલ [2] [0] = 3.

પછી તપાસો કે આઉટપુટ <વલ [i] [જે] સાચું પાછું આવે છે અને આઉટપુટ = વાલ [2] [0] કરે છે.

આઉટપુટ = 3;

અને આ પુનરાવર્તિત એરેની મહત્તમ લંબાઈ હશે જે is છે પછી પણ જો આપણે તત્વોને ટ્રversવર્સિંગમાં સમાન ગણીએ છીએ પરંતુ તે આઉટપુટમાં અપડેટ કરશે નહીં, કારણ કે તે સબઅરે નહીં

ચાલો હું = 1, j = 1 પર કહીએ કે આપણે આગામી સમાન તત્વ શોધીશું જેથી તે વાલ [1] [1] = વાલ [2] [2] +1 કરશે;

અને જો આપણે આઉટપુટ <વલ [1] [1] તપાસો તો તે દર વખતે ખોટું આપે છે અને કંઇ કરશે નહીં.

અહીં, આઉટપુટ 3 છે.

અમલીકરણ

પુનરાવર્તિત સબબ્રેની મહત્તમ લંબાઈ માટે સી ++ પ્રોગ્રામ

#include <iostream>
using namespace std;

int lengthOfRepeatedArray(int array1[], int array2[])
{
    int output = 0;
    int val[6][6]= {0};

    for (int i = 4; i >= 0; --i)
    {
        for (int j = 4; j >= 0; --j)
        {
            if (array1[i] == array2[j])
            {
                val[i][j] = val[i+1][j+1] + 1;
                if(output < val[i][j])
                {
                    output = val[i][j];
                }
            }
        }
    }
    return output;
}
int main()
{
    int a[]= {1,2,3,2,1};
    int b[]= {3,2,1,4,7};

    cout<<lengthOfRepeatedArray(a,b);
    return 0;
}
3

પુનરાવર્તિત સબબ્રેની મહત્તમ લંબાઈ માટે જાવા પ્રોગ્રામ

class repeatedArrayLength
{
    public static int lengthOfRepeatedArray(int[] array1, int[] array2)
    {
        int output = 0;
        int val[][] = new int[array1.length + 1][array2.length + 1];
        for (int i = array1.length - 1; i >= 0; --i)
        {
            for (int j = array2.length - 1; j >= 0; --j)
            {
                if (array1[i] == array2[j])
                {
                    val[i][j] = val[i+1][j+1] + 1;
                    if(output < val[i][j])
                        output = val[i][j];
                }
            }
        }
        return output;
    }
    public static void main(String []args)
    {
        int a[]= {1,2,3,2,1};
        int b[]= {3,2,1,4,7};
        System.out.println(lengthOfRepeatedArray(a,b));
    }
}
3

પુનરાવર્તિત સબબ્રેની મહત્તમ લંબાઈ માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એ × બી) જ્યાં "એ" પ્રથમ એરેનું કદ છે અને “બી” બીજા એરેનું કદ છે.

અવકાશ જટિલતા

ઓ (એ × બી) જ્યાં "એ" પ્રથમ એરેનું કદ છે અને “બી” બીજા એરેનું કદ છે.

સંદર્ભ