લાંબો અનુગામી જેમ કે અડીને વચ્ચેનો તફાવત એક છે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન અવલારા ફેક્ટસેટ ફોરકાઇટ્સ માઈક્રોસોફ્ટ
અરે ડાયનેમિક પ્રોગ્રામિંગ એલ.આઈ.એસ.

સમસ્યા "નજીકમાં વચ્ચેનો તફાવત જેનો સૌથી લાંબો સમય છે તે એક છે" જણાવે છે કે તમને એક આપવામાં આવે છે પૂર્ણાંક એરે. હવે તમારે સૌથી લાંબી અનુગામીની લંબાઈ શોધવાની જરૂર છે કે નજીકના તત્વોનો તફાવત 1 છે.

ઉદાહરણ

લાંબો અનુગામી જેમ કે અડીને વચ્ચેનો તફાવત એક છે

1 2 3 4 7 5 9 4
6

સમજૂતી

જેમ આપણે જોઈ શકીએ છીએ કે ત્યાં બે અનુગામો છે જે સ્થિતિને અનુસરે છે. તેઓ {1, 2, 3, 4, 5, 4 are છે અને બીજો એક {7, 8} છે. તેથી સૌથી લાંબી અનુગામી એ પ્રથમ છે. આમ જવાબ 6 છે.

લાંબી અનુગામી માટેનો અભિગમ જેમ કે અડીને વચ્ચેનો તફાવત એક છે

એક નિષ્કપટ અભિગમ આવી શક્ય અનુગામીઓની પે generationી હશે. પરંતુ આપણે જાણીએ છીએ કે અનુગામી પે generationી એ ખૂબ સમય માંગવાનું કાર્ય છે. કારણ કે તેને પુનરાવર્તનની જરૂર પડશે અને તે ઘાતક સમયની જટિલતા છે. તેથી સમસ્યા હલ કરવા માટે, અમારે વધુ સારા અભિગમની જરૂર છે. વધુ સારું અભિગમ હશે ગતિશીલ પ્રોગ્રામિંગ. કારણ કે સમસ્યા એ સૌથી લાંબી વધતી પેટા અનુક્રમ જેવી જ છે. આ સમસ્યામાં, આપણે સૌથી લાંબી અનુગામી શોધવાની જરૂર છે કે જેના નજીકના તત્વોમાં 1 નો તફાવત હોવો જોઈએ. તેથી, સમસ્યાનું સમાધાન લાવવા માટે આપણે ઇનપુટ એરેના તત્વો પર પસાર થવાનું શરૂ કરીએ છીએ.

ટ્રversવર્સ કરતા પહેલાં અમે અમારું બેઝ કેસ સેટ કર્યું જે આપણું પહેલું તત્વ છે. આપણે હંમેશાં 1 લંબાઈનો અનુગામી બનાવી શકીએ છીએ. જો આપણે એક તત્વ પસંદ કરીએ. હવે જેમ જેમ આપણે આગળ વધીએ છીએ, અમે એક પછાત દિશામાં તપાસ કરતા રહીશું કે જો આપણે કોઈક રીતે વર્તમાન તત્વ સાથે 1 નો સંપૂર્ણ તફાવત ધરાવતા કોઈ તત્વ શોધી કા .ીએ. તો પછી આપણે વર્તમાન ઘટકને અનુગામીમાં ઉમેરી શકીએ જે અન્ય તત્વને તેના છેલ્લા તત્વ તરીકે હતું. અને જેમ કે અમને આ પ્રકારનું તત્વ મળે છે, આપણે વર્તમાન તત્વ પર સમાપ્ત થતી અનુગામી માટેની મહત્તમ લંબાઈને અપડેટ કરવાનું ચાલુ રાખીએ છીએ. અને આ તમામ કિંમતોની ગણતરી કર્યા પછી, આપણે આ તમામ કિંમતોમાંથી મહત્તમ શોધી શકીએ છીએ. તે જ આપણી સમસ્યાનો જવાબ છે.

કોડ

સીમાંનો વચ્ચેનો તફાવત એ લાંબી પેટા અનુગામી માટે સી ++ કોડ

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

int main()
{
    int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
    int n = (sizeof input)/(sizeof input[0]);
    int dp[n];memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for(int i=1;i<n;i++){
        for(int j=i;j>=0;j--)
            if(abs(input[i]-input[j]) == 1)
                dp[i] = max(dp[i], dp[j]+1);
    }
    int answer = 0;
    for(int i=0;i<n;i++)
        answer = max(answer, dp[i]);
    cout<<answer;
}
6

લાંબી અનુગામી માટે જાવા કોડ જેમ કે અડીને વચ્ચેનો તફાવત એક છે

import java.util.*;

class Main{
  public static void main(String[] args){
      int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
      int n = input.length;
      int dp[] = new int[n];
      for(int i=1;i<n;i++)dp[i] = 0;

      dp[0] = 1;
      for(int i=1;i<n;i++){
          for(int j=i;j>=0;j--)
              if(Math.abs(input[i]-input[j]) == 1)
                  dp[i] = Math.max(dp[i], dp[j]+1);
      }
      int answer = 0;
      for(int i=0;i<n;i++)
          answer = Math.max(answer, dp[i]);
      System.out.print(answer);
  }
}
6

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન ^ 2), કારણ કે અમારી પાસે બે આંટીઓ હતી. એક ખાલી બધા તત્વો ઉપરથી પસાર થતો હતો અને બીજો એક તે બધા તત્વો પર પસાર થતો હતો જે પથરાયેલા છે. આમ અલ્ગોરિધમનો સમય જટિલતા બહુપદી બની જાય છે.

અવકાશ જટિલતા

ઓ (એન), કારણ કે આપણે તે બધા તત્વો માટે પરિણામ સંગ્રહિત કરવું પડ્યું હતું જે આપણે અત્યાર સુધી ચાલ્યા હતા. આમ જગ્યા જટિલતા રેખીય છે.