ಗರಿಷ್ಠ ಉದ್ದದ ಹಾವಿನ ಅನುಕ್ರಮವನ್ನು ಹುಡುಕಿ  


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಕೋಡ್‌ನೇಷನ್ Expedia ಯಾಂಡೆಕ್ಸ್
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್

“ಗರಿಷ್ಠ ಉದ್ದದ ಹಾವಿನ ಅನುಕ್ರಮವನ್ನು ಹುಡುಕಿ” ಎಂಬ ಸಮಸ್ಯೆ ನಮಗೆ ಒದಗಿಸಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಗ್ರಿಡ್ ಹೊಂದಿರುವ ಪೂರ್ಣಾಂಕಗಳು. ಗರಿಷ್ಠ ಉದ್ದದೊಂದಿಗೆ ಹಾವಿನ ಅನುಕ್ರಮವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಕಾರ್ಯವಾಗಿದೆ. 1 ರ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸದೊಂದಿಗೆ ಗ್ರಿಡ್‌ನಲ್ಲಿ ಪಕ್ಕದ ಸಂಖ್ಯೆಗಳನ್ನು ಹೊಂದಿರುವ ಅನುಕ್ರಮವನ್ನು ಹಾವಿನ ಅನುಕ್ರಮ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಒಂದು ಸಂಖ್ಯೆಯ ಪಕ್ಕದ ಅಂಶಗಳು ಗ್ರಿಡ್ ಒಳಗೆ ಅಸ್ತಿತ್ವದಲ್ಲಿರುವುದರಿಂದ ಅದು ಎಡ ಮತ್ತು ನೆರೆಹೊರೆಯ ಮೇಲಿರುವ ಸಂಖ್ಯೆಗಳು. Ly ಪಚಾರಿಕವಾಗಿ ಹೇಳುವುದಾದರೆ, ನೀವು ಗ್ರಿಡ್‌ನಲ್ಲಿರುವ (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

ವಿವರಣೆ

ಗರಿಷ್ಠ ಉದ್ದದ ಹಾವಿನ ಅನುಕ್ರಮವನ್ನು ಹುಡುಕಿ

ಅಪ್ರೋಚ್  

ಸಮಸ್ಯೆಯು ಹಾವಿನ ಅನುಕ್ರಮವನ್ನು ಗರಿಷ್ಠ ಉದ್ದದೊಂದಿಗೆ ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ ಮತ್ತು ನಮಗೆ ಇನ್ಪುಟ್ ಆಗಿ ಗ್ರಿಡ್ ಅನ್ನು ಒದಗಿಸಲಾಗಿದೆ. ಗ್ರಿಡ್ನ ಮೇಲಿನ ಎಡ ಮೂಲೆಯಿಂದ ಪ್ರಾರಂಭಿಸುವುದು ನಿಷ್ಕಪಟ ಅಥವಾ ವಿವೇಚನಾರಹಿತ ವಿಧಾನವಾಗಿದೆ, ಮತ್ತು ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸುವುದು ಅದರ ಬಲ ಮತ್ತು ಕೆಳಗಿನ ನೆರೆಹೊರೆಯ ಮೂಲಕ ಹೋಗುತ್ತದೆ. ಅದೇ ರೀತಿ ಆ ಕೋಶಗಳಿಂದ ತಮ್ಮ ನೆರೆಹೊರೆಯವರಿಗೆ ಹೋಗಿ ಮತ್ತು ನೀವು ಕೋಶವನ್ನು ಕಂಡುಕೊಳ್ಳುವವರೆಗೂ ಮುಂದುವರಿಯುವುದು ಷರತ್ತುಗಳ ಕಾರಣದಿಂದಾಗಿ ಮುಂದೆ ಸಾಗುವುದು ಒಂದು ಆಯ್ಕೆಯಾಗಿಲ್ಲ. ಸಾಮಾನ್ಯವಾಗಿ ನಾವು ನಾಲ್ಕು ಪುನರಾವರ್ತಿತ ಕರೆಗಳನ್ನು ಹೊಂದಿರುವ ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸುವುದರಿಂದ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಹೆಚ್ಚಿನ ಭಾಗದಲ್ಲಿರುತ್ತದೆ.

ಮೇಲಿನ ವಿಧಾನದ ಬದಲು, ನಾವು ಹೋಗಬಹುದು ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಏಕೆಂದರೆ ನಾವು ಪುನರಾವರ್ತಿತ ಪರಿಹಾರವನ್ನು ಬಳಸಿಕೊಂಡು ಸಮಸ್ಯೆಯನ್ನು ವಿವರಿಸುತ್ತೇವೆ. ನಂತರ ಪರಿಹಾರವನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿಸಲು ಅದನ್ನು ಜ್ಞಾಪಕದಲ್ಲಿರಿಸಿಕೊಳ್ಳಿ. ಮೇಲಿನ ವಿಧಾನದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಘಾತೀಯ ಆದರೆ ಬಳಸುವುದು ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅದನ್ನು ಬಹುಪದಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಬಹುದು. ಈ ಸಮಸ್ಯೆಗೆ, ನಾವು ಮೊದಲು ಎರಡು ರಾಜ್ಯಗಳನ್ನು ನೋಡುತ್ತೇವೆ ಸಾಲು ಸೂಚ್ಯಂಕ ಮತ್ತು ನಂತರ ಕಾಲಮ್ ಸೂಚ್ಯಂಕ. ಡಿಪಿ ಕೋಷ್ಟಕದಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಕೋಶವು ಅದರ ಮೇಲಿನ ಮತ್ತು ಎಡ ಕೋಶವನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ. ಉತ್ತರಕ್ಕಾಗಿ ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತಿರುವ ಕೋಶಗಳು ನಮಗೆ ಅಗತ್ಯವಿದ್ದರೆ, ನಾವು ಡಿಪಿ ಟೇಬಲ್ ಮೇಲೆ ಮತ್ತು ಪ್ರತಿ ಕೋಶದ ಫಲಿತಾಂಶದ ಪ್ರಕಾರ ಸಂಚರಿಸುತ್ತೇವೆ. ಅನುಕ್ರಮವನ್ನು ರೂಪಿಸಲು ಯಾವ ಕೋಶವನ್ನು ತೆಗೆದುಕೊಳ್ಳಲಾಗಿದೆ ಎಂದು ನಾವು ನಿರ್ಧರಿಸುತ್ತೇವೆ.

ಸಹ ನೋಡಿ
ಪತ್ರ ಪ್ರಕರಣ ಕ್ರಮಪಲ್ಲಟನೆ

ಕೋಡ್  

ಗರಿಷ್ಠ ಉದ್ದದ ಹಾವಿನ ಅನುಕ್ರಮವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#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 ನಿಯಮಗಳನ್ನು ಮುದ್ರಿಸಿ

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎಂ), ಏಕೆಂದರೆ ನಾವು ಇನ್ಪುಟ್ ಗ್ರಿಡ್ನ ಗಾತ್ರದ ಡಿಪಿ ಗ್ರಿಡ್ ಅನ್ನು ರಚಿಸುತ್ತೇವೆ.