अधिकतम लंबाई सर्प अनुक्रम ज्ञात करें


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना कोडेशन Expedia Yandex
गतिशील प्रोग्रामिंग मैट्रिक्स

समस्या "अधिकतम लंबाई सांप अनुक्रम खोजें" में कहा गया है कि हम एक के साथ प्रदान की जाती हैं ग्रिड युक्त पूर्णांकों। कार्य एक सांप अनुक्रम को अधिकतम लंबाई के साथ ढूंढना है। ग्रिड के समीप 1 के निरपेक्ष अंतर के साथ संख्याओं के अनुक्रम को स्नेक अनुक्रम के रूप में जाना जाता है। एक संख्या के लिए आसन्न तत्व संख्याएं हैं जो इसे छोड़ दिया गया है और पड़ोसियों से ऊपर है, यह देखते हुए कि वे ग्रिड के अंदर मौजूद हैं। औपचारिक रूप से, यदि आप ग्रिड में (i, j) सेल में खड़े हैं, तो कोशिकाएं (i, j-1), (i-1, j) इस से सटे हैं कि वे ग्रिड के अंदर स्थित हैं।

उदाहरण

3 3// dimensions of grid
1 2 3
2 4 5
1 2 1
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

व्याख्या

अधिकतम लंबाई सर्प अनुक्रम ज्ञात करें

दृष्टिकोण

समस्या अधिकतम लंबाई के साथ सांप अनुक्रम को खोजने के लिए कहती है और हमें एक इनपुट के रूप में ग्रिड के साथ प्रदान किया जाता है। एक भोली या जानवर बल दृष्टिकोण ग्रिड के ऊपरी बाएं कोने से शुरू करना है, और पुनरावृत्ति का उपयोग करना अपने दाहिने और निचले पड़ोसी के माध्यम से जाता है। इसी तरह उन कोशिकाओं से उनके पड़ोसी जाते हैं और इसी तरह जब तक आपको कोई ऐसी सेल नहीं मिल जाती है जब तक कि लगाई गई शर्तों के कारण आगे बढ़ना कोई विकल्प नहीं है। पुनरावर्तन का उपयोग करना जहां सामान्य रूप से हमारे पास चार पुनरावर्ती कॉल होते हैं, समय जटिलता उच्च पक्ष पर होने वाली है।

उपरोक्त दृष्टिकोण के बजाय, हम साथ जा सकते हैं गतिशील प्रोग्रामिंग क्योंकि हम पुनरावर्ती समाधान का उपयोग करके समस्या का वर्णन करते हैं। तो बस समाधान का अनुकूलन करने के लिए इसे याद रखना। उपरोक्त दृष्टिकोण के लिए समय जटिलता घातीय लेकिन उपयोग कर रहा था गतिशील प्रोग्रामिंग इसे बहुपद में घटा सकते हैं। इस समस्या के लिए, हम दो राज्यों को देखेंगे पहले पंक्ति सूचकांक और फिर स्तंभ सूचकांक है। डीपी तालिका में प्रत्येक सेल इसके ऊपर और बस बाएं सेल पर निर्भर करेगा। यदि हमें उन कोशिकाओं की भी आवश्यकता है जो उत्तर के लिए चुनी जा रही हैं, तो हम डीपी टेबल पर और प्रत्येक सेल के परिणाम के अनुसार आगे बढ़ते हैं। हम तय करते हैं कि अनुक्रम बनाने के लिए किस सेल को उठाया गया है।

कोड

C ++ कोड अधिकतम लंबाई सर्प अनुक्रम ज्ञात करने के लिए

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

int main()
{
    int n=3, m=3;
  int grid[n][m] =
  {
    {1, 2, 3},
    {2, 4, 5},
    {1, 2, 1}
  };

  int dp[n][m];
  int mx = 0, en_i = -1, en_j = -1;
  for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i][j] = 1;
            if(i>0 && abs(grid[i-1][j]-grid[i][j]) == 1)
                dp[i][j] = max(dp[i-1][j]+1, dp[i][j]);
            if(j>0 && abs(grid[i][j-1]-grid[i][j]) == 1)
                dp[i][j] = max(dp[i][j-1]+1, dp[i][j]);
            if(dp[i][j] > mx){
                mx = dp[i][j];
                en_i = i;
                en_j = j;
            }
        }
  }
  cout<<"Maximum length of the Snake Sequence is: "<<mx<<endl;
  cout<<"The maximum length snake sequence is: ";
  int l_i = -1, l_j = -1;
  while(en_i != l_i || en_j != l_j){
        cout<<grid[en_i][en_j]<<" ";
        l_i = en_i, l_j = en_j;
        if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
            en_i--;
        else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
            en_j--;
  }
}
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

जावा कोड अधिकतम लंबाई सांप अनुक्रम खोजने के लिए

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n=3, m=3;
    int grid[][] =
    {
      {1, 2, 3},
      {2, 4, 5},
      {1, 2, 1}
    };

    int dp[][] = new int[n][m];
    int mx = 0, en_i = -1, en_j = -1;
    for(int i=0;i<n;i++){
          for(int j=0;j<m;j++){
              dp[i][j] = 1;
              if(i>0 && Math.abs(grid[i-1][j]-grid[i][j]) == 1)
                  dp[i][j] = Math.max(dp[i-1][j]+1, dp[i][j]);
              if(j>0 && Math.abs(grid[i][j-1]-grid[i][j]) == 1)
                  dp[i][j] = Math.max(dp[i][j-1]+1, dp[i][j]);
              if(dp[i][j] > mx){
                  mx = dp[i][j];
                  en_i = i;
                  en_j = j;
              }
          }
    }
    System.out.println("Maximum length of the Snake Sequence is: "+mx);
    System.out.print("The maximum length snake sequence is: ");
    int l_i = -1, l_j = -1;
    while(en_i != l_i || en_j != l_j){
          System.out.print(grid[en_i][en_j]+" ");
          l_i = en_i; l_j = en_j;
          if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
              en_i--;
          else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
              en_j--;
    }
  	}
}
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

जटिलता विश्लेषण

समय जटिलता

ओ (एन * एम), जहां N और M क्रमशः पंक्तियों और स्तंभों की संख्या हैं। समय जटिलता ग्रिड के आकार पर निर्भर है। क्योंकि ग्रिड में कोशिकाओं की संख्या की गणना के लिए यह आवश्यक है। इस प्रकार सबसे खराब स्थिति में, हमें पूरी ग्रिड की यात्रा करने की आवश्यकता है।

अंतरिक्ष जटिलता

ओ (एन * एम), क्योंकि हम इनपुट ग्रिड के समान आकार का DP ग्रिड बनाते हैं।