ຜົນລວມສູງສຸດຂອງຄູ່ກັບຄວາມແຕກຕ່າງສະເພາະ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Coursera ເດລີ ສີ່ພັນ Snapdeal
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

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

ຍົກຕົວຢ່າງ

ຜົນລວມສູງສຸດຂອງຄູ່ກັບຄວາມແຕກຕ່າງສະເພາະ

42, 43, 4, 5, 6, 12
96

ຄໍາອະທິບາຍ

ພວກເຮົາເລືອກເອົາ 42, 43, ແລະ 5, 6. ພວກເຮົາມີທາງເລືອກໃນບັນດາ 4, 5, ແລະ 6. ດັ່ງນັ້ນ, ພວກເຮົາຖືເອົາມູນຄ່າສູງສຸດໃນບັນດາພວກເຂົາເຮັດໃຫ້ຜົນໄດ້ຮັບ = 96.

ວິທີການ

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

ຖ້າສະພາບການມີຄວາມເພິ່ງພໍໃຈ, ພວກເຮົາຈັບຄູ່ອົງປະກອບທີ່ຜ່ານມາແລະປັດຈຸບັນແລະເພີ່ມຜົນ ສຳ ລັບບັນຫາຈົນກ່ວາອົງປະກອບທີສອງສຸດທ້າຍ (ຈາກອົງປະກອບປັດຈຸບັນ). ແຕ່ຖ້າສະພາບການບໍ່ພໍໃຈ. ພວກເຮົາອອກຈາກການຈັບຄູ່ແລະຜົນໄດ້ຮັບແມ່ນຄືກັນກັບຂອງຈົນກ່ວາອົງປະກອບທີ່ຜ່ານມາ. ຢ່າງເປັນທາງການ, ຜົນໄດ້ຮັບ [i] = ຜົນໄດ້ຮັບ [i-2] + ວັດສະດຸປ້ອນ [i] + ວັດສະດຸປ້ອນ [i-2], ຖ້າການຈັບຄູ່ ສຳ ເລັດແລ້ວຜົນອື່ນ [i] = ຜົນ [i-1]. ນີ້ແມ່ນອາເລຜົນໄດ້ຮັບຂອງພວກເຮົາ DP array ເພາະວ່າພວກເຮົາ ກຳ ລັງເກັບມ້ຽນຜົນຂອງເຄື່ອງ ໝາຍ ນ້ອຍໆ. ພວກເຮົາສົມທົບຜົນຂອງເຄື່ອງ ໝາຍ ນ້ອຍໆເຫຼົ່ານີ້ເພື່ອຊອກຫາຜົນໄດ້ຮັບຂອງບັນຫາເດີມດັ່ງທີ່ພວກເຮົາເຮັດໃນ DP ທີ່ຢູ່ເບື້ອງລຸ່ມ.

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາຍອດລວມສູງສຸດຂອງຄູ່ກັບຄວາມແຕກຕ່າງທີ່ແນ່ນອນ

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

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}
96

ລະຫັດ Java ເພື່ອຊອກຫາຜົນລວມສູງສຸດຂອງຄູ່ທີ່ມີຄວາມແຕກຕ່າງກັນໂດຍສະເພາະ

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

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

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

O (NlogN), ນີ້ແມ່ນຍ້ອນວ່າພວກເຮົາໄດ້ຈັດລຽງ ລຳ ດັບໃນເບື້ອງຕົ້ນ. ແລະການຮວບຮວມການຈັດລຽງແລະສູດການຄິດໄລ່ການຈັດລຽງອື່ນໆສາມາດຈັດຮຽງແຖວໃນ O (NlogN). ຖ້າພວກເຮົາໄດ້ຮັບການຈັດປະເພດເຂົ້າ, ພວກເຮົາສາມາດແກ້ໄຂບັນຫາໃນເວລາ O (N).

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

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