ຜົນຊ້ ຳ ຊ້ ຳ ທີ່ຍາວທີ່ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon Arcesium Avalara ByteDance Capital One ເຟສບຸກ MetLife
ການຄົ້ນຫາຖານສອງ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ Hash string

ບັນຫາ“ ຜົນກະທົບທີ່ຊ້ ຳ ຊ້ອນຊ້ ຳ ທີ່ຍາວທີ່ສຸດ” ລະບຸວ່າທ່ານໄດ້ຮັບສາຍເປັນຂໍ້ມູນ. ຊອກຫາການຕິດຕໍ່ກັນທີ່ຍາວນານທີ່ສຸດ, ນັ້ນແມ່ນການຕິດຕໍ່ກັນທີ່ມີຢູ່ສອງຄັ້ງໃນສາຍ.

ຍົກຕົວຢ່າງ

ຜົນຊ້ ຳ ຊ້ ຳ ທີ່ຍາວທີ່ສຸດ

aeafbdfdg
3 (afd)

ວິທີການ

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

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

ລະຫັດ C ++ ເພື່ອຊອກຫາຊ້ ຳ ຊ້ອນຊ້ ຳ ທີ່ຍາວທີ່ສຸດ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s = "aeafbdfdg";
    int n = s.length();
  int dp[n][n];memset(dp, 0, sizeof dp);
  for (int i=0;i<n;i++){
    for (int j=0;j<n;j++){
      if (s[i]==s[j] && i != j) 
        dp[i][j] = 1 + ((i>0 && j>0) ? dp[i-1][j-1] : 0);
      else
        dp[i][j] = max(((j>0) ? dp[i][j-1] : 0), ((i>0) ? dp[i-1][j] : 0));
    }
  }
    cout<<dp[n-1][n-1];
}
3

ລະຫັດ Java ເພື່ອຊອກຫາຜົນກະທົບທີ່ຊ້ ຳ ຊ້ອນທີ່ຍາວທີ່ສຸດ

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    String s = "aeafbdfdg";
      int n = s.length();
    int dp[][] = new int[n+1][n+1]; 
    for (int i=0; i<=n; i++) 
      for (int j=0; j<=n; j++) 
        dp[i][j] = 0;
    for (int i=0;i<n;i++){
      for (int j=0;j<n;j++){
        if (s.charAt(i)==s.charAt(j) && i != j) 
          dp[i][j] = 1 + ((i>0 && j>0) ? dp[i-1][j-1] : 0);
        else
          dp[i][j] = Math.max(((j>0) ? dp[i][j-1] : 0), ((i>0) ? dp[i-1][j] : 0));
      }
    }
    System.out.print(dp[n-1][n-1]);
  }
}
3

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

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

O (N ^ 2), ເນື່ອງຈາກວ່າວິທີການນີ້ແມ່ນຄືກັນກັບບັນຫາຕໍ່ໄປທີ່ຍາວທີ່ສຸດ. ດັ່ງນັ້ນຄວາມສັບສົນຂອງເວລາກໍ່ຄ້າຍຄືກັນກັບນັ້ນ.

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

O (N ^ 2), ເພາະວ່າພວກເຮົາຕ້ອງສ້າງຕາຕະລາງ 2D DP. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ຍັງມີຫຼາຍຮູບແບບ.