C++-এ সর্বোচ্চ সংখ্যা তৈরি করা (Create Maximum Number)

ক্রিয়েট ম্যাক্সিমাম নাম্বার সমস্যা

দুটি অ্যারে nums1 (দৈর্ঘ্য m) এবং nums2 (দৈর্ঘ্য n) দেওয়া আছে, যেগুলো ০-৯ এর অঙ্ক ধারণ করে। এই দুটি অ্যারের অঙ্কগুলো থেকে আপেক্ষিক ক্রম রক্ষা করে দৈর্ঘ্য k (k ≤ m+n) এর সর্বোচ্চ সংখ্যা তৈরি করতে হবে।

উদাহরণ: nums1=[3,4,7,5], nums2=[9,1,3,5,8,4], k=5 → উত্তর: [9,8,7,5,4]

সমাধানের পদ্ধতি

• modify(v, k): অ্যারে v- থেকে আপেক্ষিক ক্রম রক্ষা করে দৈর্ঘ্য k এর সর্বোচ্চ সাবসিকোয়েন্স বের করুন ( মনোটোনিক স্ট্যাক ব্যবহার করে)
• mergeThem(a, b): দুটি অ্যারে a এবং b মাল্টি-ওয়ে মেড করুন যেন ফলাফল সর্বোচ্চ হয় (লেক্সিকোগ্রাফিকালি বড় প্রিফিক্স বেছে নিন)
• greater(a, b, i, j): দুটি অ্যারে লেক্সিকোগ্রাফিকালি তুলনা করুন
• মূল ফাংশন: i = 0..k এর জন্য nums1- থেকে i এবং nums2- থেকে k-i নিয়ে সব ক্যান্ডিডেট বানান এবং সর্বোচ্চটি বেছে নিন

C++ কোড উদাহরণ

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

void print_vector(vector<int> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> mergeThem(vector<int> nums1, vector<int> nums2) {
        vector<int> ret;
        int i = 0, j = 0, n = nums1.size(), m = nums2.size();
        while(i < n || j < m) {
            if(greater(nums1, nums2, i, j)) {
                ret.push_back(nums1[i]);
                i++;
            } else {
                ret.push_back(nums2[j]);
                j++;
            }
        }
        return ret;
    }
    
    vector<int> modify(vector<int>& v, int k) {
        stack<int> st;
        vector<int> ret;
        for(int i = 0; i < v.size(); i++) {
            int x = v[i];
            while(!st.empty() && st.top() < x && st.size() + (v.size() - i) - 1 >= k) {
                st.pop();
            }
            if(st.size() < k) st.push(x);
        }
        while(!st.empty()) {
            ret.push_back(st.top());
            st.pop();
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
    
    bool greater(vector<int>& a, vector<int>& b, int i, int j) {
        while(i < a.size() && j < b.size() && a[i] == b[j]) i++, j++;
        return j == b.size() || (i < a.size() && a[i] > b[j]);
    }
    
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> ret;
        int n = nums1.size(), m = nums2.size();
        for(int i = 0; i <= k; i++) {
            if(i <= n && (k - i) <= m) {
                vector<int> candidate = mergeThem(modify(nums1, i), modify(nums2, k - i));
                if(greater(candidate, ret, 0, 0)) ret = candidate;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3, 4, 7, 5}, v1 = {9, 1, 3, 5, 8, 4};
    print_vector(ob.maxNumber(v, v1, 5));
    return 0;
}

ইনপুট

{3, 4, 7, 5} {9, 1, 3, 5, 8, 4} 5

আউটপুট

[9, 8, 7, 5, 4, ]