ຊອກຫາຄວາມຍາວສູງສຸດຕາມ ລຳ ດັບງູ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon ລະຫັດປະເທດ Expedia Yandex
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ມາຕຣິກເບື້ອງ

ບັນຫາ "ຊອກ ລຳ ດັບງູທີ່ມີຄວາມຍາວສູງສຸດ" ລະບຸວ່າພວກເຮົາສະ ໜອງ ໃຫ້ກັບ a ຕາຂ່າຍໄຟຟ້າ ບັນຈຸມີ integers. ໜ້າ ວຽກແມ່ນຊອກຫາ ລຳ ດັບງູທີ່ມີຄວາມຍາວສູງສຸດ. ລໍາດັບທີ່ມີຕົວເລກທີ່ຢູ່ຕິດກັນໃນຕາຂ່າຍໄຟຟ້າທີ່ມີຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຂອງ 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

ຄໍາອະທິບາຍ

ຊອກຫາຄວາມຍາວສູງສຸດຕາມ ລຳ ດັບງູPin

ວິທີການ  

ບັນຫາຂໍໃຫ້ຊອກຫາ ລຳ ດັບງູທີ່ມີຄວາມຍາວສູງສຸດແລະພວກເຮົາໄດ້ຮັບຕາຂ່າຍໄຟຟ້າເປັນວັດສະດຸປ້ອນ. ວິທີການບັງຄັບໃຊ້ທີ່ໂງ່ຫລືເຂັ້ມແຂງແມ່ນການເລີ່ມຕົ້ນຈາກແຈເບື້ອງຊ້າຍດ້ານເທິງຂອງຕາຂ່າຍໄຟຟ້າ, ແລະການ ນຳ ໃຊ້ການເອີ້ນຄືນໂດຍຜ່ານເພື່ອນບ້ານເບື້ອງຂວາແລະລຸ່ມ. ຄ້າຍຄືກັນຈາກຈຸລັງເຫຼົ່ານັ້ນໄປທີ່ປະເທດເພື່ອນບ້ານແລະອື່ນໆຈົນກວ່າທ່ານຈະພົບເຫັນຫ້ອງດັ່ງກ່າວວ່າການກ້າວໄປຂ້າງ ໜ້າ ບໍ່ແມ່ນທາງເລືອກເພາະວ່າມີເງື່ອນໄຂທີ່ໄດ້ ກຳ ນົດໄວ້. ການ ນຳ ໃຊ້ການເອີ້ນຄືນບ່ອນທີ່ໂດຍທົ່ວໄປພວກເຮົາມີການເອີ້ນຄືນ XNUMX ຄັ້ງ, ຄວາມສັບສົນເວລາຈະຢູ່ໃນລະດັບສູງ.

ເບິ່ງ
ໃບອະນຸຍາດກໍລະນີຈົດ ໝາຍ

ແທນທີ່ຈະເປັນແນວທາງຂ້າງເທິງ, ພວກເຮົາສາມາດໄປ ນຳ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ເພາະວ່າພວກເຮົາອະທິບາຍບັນຫາໂດຍໃຊ້ວິທີແກ້ໄຂບັນຫາ. ຈາກນັ້ນພຽງແຕ່ຈົດບັນທຶກໄວ້ເພື່ອເຮັດໃຫ້ມີວິທີແກ້ໄຂທີ່ດີທີ່ສຸດ. ຄວາມສັບສົນເວລາ ສຳ ລັບວິທີການຂ້າງເທິງນີ້ແມ່ນເລກ ກຳ ລັງແຕ່ ນຳ ໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ສາມາດຫຼຸດຜ່ອນມັນເປັນ polynomial. ສຳ ລັບບັນຫານີ້, ພວກເຮົາຈະມາເບິ່ງສອງລັດກ່ອນແມ່ນດັດຊະນີແຖວແລະຫຼັງຈາກນັ້ນແມ່ນດັດຊະນີຖັນ. ແຕ່ລະຫ້ອງໃນຕາຕະລາງ DP ຈະຂື້ນກັບຫ້ອງພຽງແຕ່ຂ້າງເທິງແລະເບື້ອງຊ້າຍຂອງມັນເທົ່ານັ້ນ. ຖ້າພວກເຮົາຍັງຕ້ອງການຈຸລັງທີ່ ກຳ ລັງຖືກເລືອກໃຫ້ ຄຳ ຕອບ, ພວກເຮົາຈະຂ້າມຜ່ານຕາຕະລາງ DP ແລະອີງຕາມຜົນຂອງແຕ່ລະຫ້ອງ. ພວກເຮົາຕັດສິນໃຈວ່າຫ້ອງໃດຖືກເກັບຂື້ນເພື່ອປະກອບເປັນ ລຳ ດັບ.

ລະຫັດ  

ລະຫັດ 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

ລະຫັດ Java ເພື່ອຊອກຫາ ລຳ ດັບງູທີ່ມີຄວາມຍາວສູງສຸດ

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

ການວິເຄາະຄວາມສັບສົນ  

ຄວາມສັບສົນເວລາ

O (N * M), ບ່ອນທີ່ N ແລະ M ແມ່ນ ຈຳ ນວນແຖວແລະຖັນຕາມ ລຳ ດັບ. ຄວາມສັບສົນຂອງເວລາແມ່ນຂື້ນກັບຂະ ໜາດ ຂອງຕາຂ່າຍໄຟຟ້າ. ເພາະວ່າມັນ ຈຳ ເປັນ ສຳ ລັບການຄິດໄລ່ ຈຳ ນວນຈຸລັງໃນຕາຂ່າຍໄຟຟ້າ. ດັ່ງນັ້ນ, ໃນສະຖານະການທີ່ບໍ່ດີທີ່ສຸດ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງເດີນທາງຕາຂ່າຍໄຟຟ້າທັງ ໝົດ.

ເບິ່ງ
ພິມ n ເງື່ອນໄຂຂອງ Newman-Conway Sequence

ຄວາມສັບສົນໃນອະວະກາດ

O (N * M), ເນື່ອງຈາກວ່າພວກເຮົາສ້າງຕາຂ່າຍໄຟຟ້າ DP ທີ່ມີຂະ ໜາດ ເທົ່າກັບຕາຂ່າຍໄຟຟ້າປ້ອນເຂົ້າ.