ພິມຕ່ອງໂສ້ຄວາມຍາວສູງສຸດຂອງຄູ່


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

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

ບັນຫາ“ ຕ່ອງໂສ້ຄວາມຍາວສູງສຸດຂອງຄູ່ພິມ” ລະບຸວ່າທ່ານໄດ້ຮັບ ຈຳ ນວນຄູ່ຄູ່. ມັນໄດ້ຖືກມອບໃຫ້ໃນແຕ່ລະຄູ່, ຕົວເລກທໍາອິດແມ່ນນ້ອຍກວ່າຈໍານວນທີສອງ. ຕອນນີ້ທ່ານ ຈຳ ເປັນຕ້ອງຊອກຫາຕ່ອງໂສ້ທີ່ຍາວທີ່ສຸດເຊັ່ນວ່າຕົວເລກທີ່ສອງຂອງຄູ່ກ່ອນ ໜ້າ (ກ, ຂ) ແມ່ນນ້ອຍກວ່າ ຈຳ ນວນ ທຳ ອິດຂອງຄູ່ຕໍ່ໄປຫຼັງຈາກຄູ່ (c, d) ນັ້ນແມ່ນ (b <c).

ຍົກຕົວຢ່າງ

(1, 10), (11, 25), (26, 35), (36, 50)
(1, 10), (11, 25), (26, 35), (36, 50)

ຄໍາອະທິບາຍ

ພວກເຮົາຄັດເລືອກຄູ່ທັງ ໝົດ ເພາະວ່າທັງ ໝົດ ຂອງຄູ່ທີ່ໄດ້ຮັບແມ່ນພໍໃຈກັບສະພາບການ.

(1, 2), (10, 30), (5, 6), (15, 25), (17, 21)
(1, 2), (5, 6), (10, 30)

ຄໍາອະທິບາຍ

ຄູ່ທີສາມທີ່ພວກເຮົາເລືອກບໍ່ ສຳ ຄັນ. ພວກເຮົາສາມາດເລືອກເອົາສາມຄູ່ທີ່ຍັງເຫຼືອເພາະວ່າພວກເຂົາທັງ ໝົດ ພໍໃຈກັບສະພາບການ. ແຕ່ພວກເຮົາບໍ່ສາມາດເລືອກເອົາສອງໃນສາມຂອງສ່ວນທີ່ເຫຼືອ.

ວິທີການພິມຕ່ອງໂສ້ຄວາມຍາວສູງສຸດຂອງຄູ່

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

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

ດັ່ງນັ້ນ, ການພົວພັນກັບການເກີດຂື້ນຄືນ ໃໝ່ ແມ່ນ

ພິມຕ່ອງໂສ້ຄວາມຍາວສູງສຸດຂອງຄູ່

ລະຫັດ

ລະຫັດ C ++ ເພື່ອພິມຕ່ອງໂສ້ຄວາມຍາວສູງສຸດຂອງຄູ່

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


void maxChainLength(vector<pair<int,int>> &input) 
{ 
    sort(input.begin(), input.end());
  
    int n = input.size();
    vector<vector<pair<int,int>>> dp(n); 
  	int mx = 0;
    // base case
    dp[0].push_back(input[0]); 
    for(int i=1;i<n;i++) 
    {
        for(int j=0;j<i;j++)
        {
            if ((input[j].second < input[i].first) && (dp[j].size() > dp[i].size())) // the condition must be satisfied 
                dp[i] = dp[j];
        } 
        dp[i].push_back(input[i]);
        if(dp[i].size() > dp[mx].size())
        	mx = i;
    }
    for(auto x: dp[mx])
    	cout<<"("<<x.first<<", "<<x.second<<") ";
} 

int main()
{ 
    vector<pair<int,int>> input = {{1, 2}, {10, 30}, {5, 6}, {15, 25}, {17, 21}};
    maxChainLength(input);
}
(1, 2) (5, 6) (10, 30)

ລະຫັດ Java ເພື່ອພິມຕ່ອງໂສ້ຄວາມຍາວສູງສຸດຂອງຄູ່

import java.util.*;

class Main{
    static void maxChainLength(ArrayList<ArrayList<Integer>> input)
    {
        Collections.sort(input, new Comparator<ArrayList<Integer>> () {
            @Override
            public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
                return a.get(0).compareTo(b.get(0));
            }
        });

        int n = input.size();
        ArrayList<ArrayList<ArrayList<Integer>>> dp = new ArrayList<ArrayList<ArrayList<Integer>>>();
        for(int i=0;i<n;i++)
            dp.add(new ArrayList<ArrayList<Integer>>());
        int mx = 0;
        // base case
        dp.get(0).add(input.get(0));
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(input.get(j).get(1) < input.get(i).get(0) && (dp.get(j).size() > dp.get(i).size())){
                    dp.set(i, new ArrayList<ArrayList<Integer>>(dp.get(j)));
                }
            }
            dp.get(i).add(input.get(i));
            if(dp.get(i).size() > dp.get(mx).size())
                mx = i;
        }
        for(ArrayList<Integer> x: dp.get(mx))
            System.out.print("("+x.get(0)+", "+x.get(1)+") ");
    }

    public static void main(String[] args)
    {
        ArrayList<ArrayList<Integer>> input = new ArrayList<ArrayList<Integer>>();
        input.add(new ArrayList(Arrays.asList(1, 2)));
        input.add(new ArrayList(Arrays.asList(10, 30)));
        input.add(new ArrayList(Arrays.asList(5, 6)));
        input.add(new ArrayList(Arrays.asList(15, 25)));
        input.add(new ArrayList(Arrays.asList(17, 21)));
        maxChainLength(input);
    }
}
(1, 2) (5, 6) (10, 30)

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

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

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

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

O (N ^ 2), ຄວາມສັບສົນໃນພື້ນທີ່ຍັງມີຫຼາຍຮູບແບບເພາະວ່າພວກເຮົາໄດ້ໃຊ້ vector ຂອງ vector. ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດເມື່ອຄວາມຍາວຂອງຕ່ອງໂສ້ສູງສຸດເທົ່າກັບຂະ ໜາດ ຂອງວັດສະດຸປ້ອນ. ຫຼັງຈາກນັ້ນ vector ຂອງ vector ຂອງພວກເຮົາຈະມີ O (N ^ 2) ຄູ່. ດັ່ງນັ້ນພື້ນທີ່ທີ່ຕ້ອງການກໍ່ຍັງມີຫຼາຍຮູບແບບເຊັ່ນກັນ.