ຜະລິດຕະພັນສູງສຸດຂອງການຕິດຕໍ່ທີ່ເພີ່ມຂື້ນ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ GE Healthcare ແຮກເກີຣ IBM SnapChat Yahoo
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ຖະແຫຼງການບັນຫາ

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

ຍົກຕົວຢ່າງ

ຜະລິດຕະພັນສູງສຸດຂອງການຕິດຕໍ່ທີ່ເພີ່ມຂື້ນ

10, 1, 1000, 2, 3, 4
10000

ຜະລິດຕະພັນສູງສຸດຂອງການຕິດຕາມທີ່ເພີ່ມຂື້ນແມ່ນ 10, 1000. ເຖິງແມ່ນວ່າການຕິດຕໍ່ກັນທີ່ຍາວທີ່ສຸດແມ່ນ {1, 2, 3, 4}.

ວິທີການ

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

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

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

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາຜະລິດຕະພັນສູງສຸດຂອງການຕິດຕາມທີ່ເພີ່ມຂື້ນ

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


int maxProductOfIncreasingSubsequence(vector<int> &input){
  vector<int> dp(n);
  dp[0] = input[0];
  int ans = input[0];
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(input[j] < input[i])
        dp[i] = max(dp[i], dp[j]*input[i]);
    }
    ans = max(ans, dp[i]);
  }
  return ans;
}

int main(){
  int n;cin>>n;
  vector<int> input(n);
  for(int i=0;i<n;i++)
    cin>>input[i];

  cout<<maxProductOfIncreasingSubsequence(input);
}
6
10 1 1000 2 3 4
10000

ລະຫັດ Java ເພື່ອຊອກຫາຜະລິດຕະພັນສູງສຸດຂອງການຕິດຕາມທີ່ເພີ່ມຂື້ນ

import java.util.*;

class Main{
    static int maxProductOfIncreasingSubsequence(ArrayList<Integer> input){
    ArrayList<Integer> dp = new ArrayList<Integer>();
    dp.add(input.get(0));
    int ans = input.get(0);
    int n = input.size();
    for(int i=1;i<n;i++){
      dp.add(input.get(i));
      for(int j=0;j<i;j++){
        if(input.get(j) < input.get(i))
          dp.set(i, Math.max(dp.get(i), dp.get(j)*input.get(i)));
      }
      ans = Math.max(ans, dp.get(i));
    }
    return ans;
  }

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> input = new ArrayList<>();
    for(int i=0;i<n;i++){
      int in = sc.nextInt();
      input.add(in);
    }

    int answer = maxProductOfIncreasingSubsequence(input);
    System.out.print(answer);
  }
}
6
10 1 1000 2 3 4
10000

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

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

O (N ^ 2) ເພາະວ່າພວກເຮົາ ກຳ ລັງໃຊ້ສອງວົງແຫວນທີ່ມີຮັງ. ຫນຶ່ງທີ່ແລ່ນໃນທົ່ວທຸກອົງປະກອບແລະວົງພາຍໃນອື່ນໆແລ່ນ ເໜືອ ທຸກອົງປະກອບຈົນກ່ວາປັດຈຸບັນນີ້.

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

O (N) ເພາະວ່າພວກເຮົາສ້າງຕາຕະລາງ DP ຂະ ໜາດ ດຽວ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນເປັນເສັ້ນ.