ຕໍ່ມາດົນທີ່ສຸດເຊັ່ນວ່າຄວາມແຕກຕ່າງລະຫວ່າງຄວາມໃກ້ຊິດແມ່ນ ໜຶ່ງ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Avalara ປັດໃຈ ສີ່ພັນ Microsoft
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ Lis

ບັນຫາ "ຕໍ່ມາດົນນານທີ່ສຸດເຊັ່ນວ່າຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຊົ່ວຊ້າແມ່ນ ໜຶ່ງ" ທີ່ທ່ານໄດ້ຮັບໃຫ້ integer array. ໃນປັດຈຸບັນທ່ານຈໍາເປັນຕ້ອງຊອກຫາຄວາມຍາວຂອງການຕິດຕໍ່ທີ່ຍາວທີ່ສຸດເຊັ່ນວ່າຄວາມແຕກຕ່າງຂອງອົງປະກອບທີ່ຢູ່ຕິດກັນແມ່ນ 1.

ຍົກຕົວຢ່າງ

ຕໍ່ມາດົນທີ່ສຸດເຊັ່ນວ່າຄວາມແຕກຕ່າງລະຫວ່າງຄວາມໃກ້ຊິດແມ່ນ ໜຶ່ງ

1 2 3 4 7 5 9 4
6

ຄໍາອະທິບາຍ

ດັ່ງທີ່ພວກເຮົາສາມາດເຫັນໄດ້ວ່າມີສອງຢ່າງຕໍ່ເນື່ອງທີ່ຕິດຕາມສະພາບການ. ພວກມັນແມ່ນ {1, 2, 3, 4, 5, 4} ແລະອີກອັນ ໜຶ່ງ ແມ່ນ {7, 8}. ດັ່ງນັ້ນການຕິດຕໍ່ທີ່ຍາວທີ່ສຸດແມ່ນຜູ້ ທຳ ອິດ. ສະນັ້ນ ຄຳ ຕອບແມ່ນ 6.

ວິທີການ ສຳ ລັບການຕິດຕໍ່ທີ່ຍາວທີ່ສຸດເຊັ່ນວ່າຄວາມແຕກຕ່າງລະຫວ່າງຄວາມໃກ້ຊິດແມ່ນ ໜຶ່ງ

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

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

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບການຕິດຕໍ່ທີ່ຍາວທີ່ສຸດເຊັ່ນວ່າຄວາມແຕກຕ່າງລະຫວ່າງຄວາມໃກ້ຊິດແມ່ນ ໜຶ່ງ

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

int main()
{
    int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
    int n = (sizeof input)/(sizeof input[0]);
    int dp[n];memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for(int i=1;i<n;i++){
        for(int j=i;j>=0;j--)
            if(abs(input[i]-input[j]) == 1)
                dp[i] = max(dp[i], dp[j]+1);
    }
    int answer = 0;
    for(int i=0;i<n;i++)
        answer = max(answer, dp[i]);
    cout<<answer;
}
6

ລະຫັດ Java ສຳ ລັບການຕິດຕໍ່ທີ່ຍາວທີ່ສຸດເຊັ່ນວ່າຄວາມແຕກຕ່າງລະຫວ່າງຄວາມໃກ້ຊິດແມ່ນ ໜຶ່ງ

import java.util.*;

class Main{
  public static void main(String[] args){
      int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
      int n = input.length;
      int dp[] = new int[n];
      for(int i=1;i<n;i++)dp[i] = 0;

      dp[0] = 1;
      for(int i=1;i<n;i++){
          for(int j=i;j>=0;j--)
              if(Math.abs(input[i]-input[j]) == 1)
                  dp[i] = Math.max(dp[i], dp[j]+1);
      }
      int answer = 0;
      for(int i=0;i<n;i++)
          answer = Math.max(answer, dp[i]);
      System.out.print(answer);
  }
}
6

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

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

O (N ^ 2), ເນື່ອງຈາກວ່າພວກເຮົາມີສອງ loops. ຫນຶ່ງແມ່ນພຽງແຕ່ traversing ໃນອົງປະກອບທັງຫມົດແລະຫນຶ່ງແມ່ນ traversing ໃນອົງປະກອບທັງຫມົດທີ່ໄດ້ຮັບການ traversed. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາສໍາລັບສູດການກາຍເປັນ polynomial.

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

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາຕ້ອງເກັບຮັກສາຜົນໄດ້ຮັບ ສຳ ລັບທຸກໆສ່ວນປະກອບທີ່ພວກເຮົາໄດ້ຜ່ານມາຈົນເຖິງປະຈຸບັນ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນເປັນເສັ້ນ.