שלאַנג סיקוואַנס פֿאַר מאַקסימום לענג  


שוועריקייט לעוועל שווער
אָפט געבעטן אין אַמאַזאָן קאָדנאַטיאָן עקספּעדיאַ יאַנדעקס
דינאַמיש פּראָגראַממינג מאַטריץ

די פּראָבלעם "געפֿינען מאַקסימום לענג שלאַנג סיקוואַנס" שטאַטן אַז מיר זענען צוגעשטעלט מיט אַ גריד מיט ינטאַדזשערז. די אַרבעט איז צו געפֿינען אַ שלאַנג סיקוואַנס מיט די מאַקסימום לענג. א סיקוואַנס מיט שכייניש נומערן אין די גריד מיט אַן אַבסאָלוט חילוק פון 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), וווּ N און M זענען די נומער פון ראָוז און שפאלטן ריספּעקטיוולי. די צייט קאַמפּלעקסיטי איז אָפענגיק אויף די גרייס פון דעם גריד. ווייַל עס איז פארלאנגט פֿאַר קאַלקיאַלייטינג די נומער פון סעלז אין די גריד. אין דעם ערגסט פאַל, מיר דאַרפֿן צו אַרומפאָרן די גאנצע גריד.

זע אויך
דרוקן טערמינען פון Newman-Conway סיקוואַנס

ספעיס קאַמפּלעקסיטי

אָ (N * M), ווייַל מיר מאַכן די דפּ גריד פון די זעלבע גרייס ווי די פון די אַרייַנשרייַב גריד.