C++-এ সর্বাধিক K মুভের পরিসরে [L, R] সংখ্যার যোগফল সর্বাধিক করুন

আমাদের একটি অ্যারে দেওয়া হয়েছে Arr[] যাতে পূর্ণসংখ্যা থাকে এবং 2D অ্যারে Q থাকে। প্রতিটি ক্যোয়ারীতে 3টি মান রয়েছে যা হল lpos, rpos এবং K। একজন একক ধাপে সূচী i থেকে পরবর্তী সূচক i+1 এ যেতে পারে বা সেই সূচকে থাকতে পারে। কেউ lpos থেকে rpos-এ সর্বাধিক K ধাপে যেতে পারে। বামদিকের সংখ্যা সহ প্রতিটি ধাপে সমস্ত সংখ্যা যোগ করুন। লক্ষ্য হল সর্বাধিক K চালে যোগফল সর্বাধিক করা। যদি K ধাপে lpos থেকে rpos পর্যন্ত কোনো নড়াচড়া সম্ভব না হয় তাহলে "No" প্রিন্ট করুন। আসুন আমরা আরও বুঝতে পারি।

আসুন এর জন্য বিভিন্ন ইনপুট আউটপুট পরিস্থিতি দেখি -

এ − Arr[] ={1, 2, 4, -1 };

প্রশ্ন[][3] ={ { 0, 2, 2 }, { 0, 2, 1 }, { 3, 3, 1 }, { 0, 2, 3} };

আউট −

প্রশ্ন 1:7

প্রশ্ন 2:না

প্রশ্ন 3:না

প্রশ্ন 4:11

ব্যাখ্যা −

প্রথম প্রশ্ন:-

আমরা সর্বোচ্চ 2টি ধাপে সূচক 0 থেকে 2 পর্যন্ত যেতে পারি:-

ধাপ 1:- সূচক 0 থেকে 1 ( 1+2=3 )

ধাপ 2:- সূচক 1 থেকে 2 ( 3+4=7)

দ্বিতীয় প্রশ্ন:-

আমরা সর্বোচ্চ 1 ধাপে সূচক 0 থেকে 2 পর্যন্ত যেতে পারি না। "না"

প্রিন্ট করুন

তৃতীয় প্রশ্ন:-

আমরা সর্বোচ্চ 1 ধাপে সূচক 3 থেকে 3 এ যেতে পারি না। "না"

প্রিন্ট করুন

চতুর্থ প্রশ্ন:-

আমরা সর্বাধিক 3টি ধাপে সূচক 0 থেকে 2 পর্যন্ত যেতে পারি:-

ধাপ 1:- সূচক 0 থেকে 1 ( 1+2=3 )

ধাপ 2:- সূচক 1 থেকে 2 ( 3+4=7)

ধাপ 3:- সূচক 2 এ থাকুন ( 7+4=11)

এ − Arr[] ={ 1, 2, 3, 3, 2 }; প্রশ্ন[][3] ={ { 0, 3, 2 }, { 1, 4, 3 } };

আউট −

প্রশ্ন 1:না

প্রশ্ন 2:10

ব্যাখ্যা −

প্রথম প্রশ্ন:-

আমরা সর্বোচ্চ 1 ধাপে সূচক 0 থেকে 2 পর্যন্ত যেতে পারি না। “না” প্রিন্ট করুন

দ্বিতীয় প্রশ্ন:-

আমরা সর্বাধিক 3টি ধাপে সূচক 1 থেকে 4 এ যেতে পারি:-

ধাপ 1:- সূচক 1 থেকে 2 ( 2+3=5 )

ধাপ 2:- সূচক 2 থেকে 3 ( 5+3=8 )

ধাপ 3:- সূচক 3 থেকে 4 ( 8+2=10)

নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি

এই পদ্ধতিতে আমরা সম্ভাব্য সর্বাধিক মান খুঁজে পেতে এবং উপসর্গ যোগফল ব্যবহার করে সমস্ত সংখ্যার যোগফল গণনা করতে lpos থেকে rpos পরিসরের জন্য সেগমেন্ট ট্রি ব্যবহার করব।

ইনপুট অ্যারে Arr[] এবং প্রশ্ন ম্যাট্রিক্স Q[][].
নিন
সেগমেন্ট ট্রি বাস্তবায়নের জন্য অ্যারে হিসাবে sgTree[5 * length] নিন।
প্রিফিক্স যোগ অ্যারে হিসাবে pSum[দৈর্ঘ্য] নিন।
ফাংশন createTree(int min, int max, int pos, int sgT[], int arr[], int len) একটি সেগমেন্ট ট্রিতে মান তৈরি করতে ব্যবহৃত হয়।
পরীক্ষা করুন যদি (মিনিট ==সর্বোচ্চ) যার মানে এটি একটি লিফ নোড। sgT[pos] =arr[max]।
সেট করুন
মাঝামাঝি =(মিনিট + সর্বোচ্চ) / 2।
নিন
CreateTree(min,midd, loc1, sgT, arr, len) এবং CreateTree(midd + 1, max, loc2, sgT, arr, len) কল করুন বাম এবং ডান সাবট্রির জন্য যেখানে loc1=2*pos+1 এবং loc2=2* pos+2।
tmp1=sgT[loc1] এবং tmp2=sgT[loc2] নিন এবং sgT[pos] আপডেট করুন tmp1 বা tmp2 যেটি সর্বাধিক।
ফাংশন preSum(int pSum4[], int arr4[], int len4) ইনপুট অ্যারে নেয় এবং লুপের জন্য ব্যবহার করে উপসর্গ অ্যারে আপডেট করে৷
সূচক 1 থেকে শেষ পর্যন্ত প্রতিটি উপাদানের জন্য, pSum4[j] =pSum4[j - 1] + arr4[j];
আপডেট করুন
ফাংশন resQuery(int len3, int arr3[], int sgT3[], int pSum3[], int q1[][3], int qlen1) সমস্ত ইনপুট প্যারামিটার নেয় এবং প্রতিটি প্রশ্নের জন্য ফলাফল প্রিন্ট করে।
ইনসাইড resQuery(), solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) লুপ ব্যবহার করে একে একে প্রতিটি প্রশ্নের সমাধান করতে কল করুন৷
ফাংশন solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) প্রশ্নের সমাধান করে এবং ফলাফল প্রদান করে।
যদি rpos - lpos> k হয় তাহলে -1 রিটার্ন করুন কারণ কোন সমাধান সম্ভব নয়।
maxVal =findMax(0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2) নিন;
যদি maxVal <0 হয় তাহলে maxVal কে 0
হিসেবে সেট করুন
পরিবর্তনশীল যোগফল =pSum2[rpos] নিন।
যদি lpos> 0 হয় তাহলে যোগফল -=pSum2[lpos - 1] এবং ফলাফল =যোগফল + (k - (rpos - lpos)) * maxVal সেট করুন।
ফলাফল ফেরত।
ফাংশন FindMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1) রেঞ্জ lpos এবং rpos এর মধ্যে সর্বাধিক মান প্রদান করে৷
যদি (min1 <=start) এবং ( max1>=end) তাহলে sgT1[pos1] ফেরত দিন কারণ ওভারল্যাপ আছে।
যদি (শেষ max1) তাহলে সীমার বাইরে ঘটছে তাই INT_MIN ফেরত দিন।
বাম এবং ডান সাবট্রির জন্য রিকার্সিভ কল ব্যবহার করে lmax এবং rmax গণনা করুন এবং সর্বাধিক দুটি রিটার্ন করুন।
শেষে প্রতিটি প্রশ্নের জন্য ফলাফল প্রিন্ট করা হবে। "না" যদি কোন সমাধান না হয়

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
void createTree(int min, int max, int pos,
int sgT[], int arr[], int len){ if (min == max) {
   sgT[pos] = arr[max];
   return;
   }
   int midd = (min + max) / 2;
   int loc1=2*pos+1;
   int loc2=2*pos+2;
   createTree(min, midd, loc1, sgT, arr, len);
   createTree(midd + 1, max, loc2, sgT, arr, len);
   int tmp1=sgT[loc1];
   int tmp2=sgT[loc2];
   sgT[pos] = tmp1>tmp2 ? tmp1 : tmp2 ;
}
int findMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1){
   int middle;
   if (min1 <= start)
   { if( max1 >= end){
         return sgT1[pos1];
      }
   }
   if (end < min1 || start > max1)
   { return INT_MIN; }

   middle = (start + end) / 2;
   int loc1=2 * pos1 + 1;
   int loc2=2 * pos1 + 2;
   int lmax = findMax(start, middle, min1, max1, loc1, sgT1, arr1, len1);
   int rmax = findMax(middle + 1, end, min1, max1, loc2, sgT1, arr1, len1);
   int res=lmax>rmax?lmax:rmax;
   return res;
}
int solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]){
   int result;
      if (rpos - lpos > k)
      { return -1; }
      int maxVal = findMax(0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2);
      if (maxVal < 0)
      { maxVal = 0; }
      int sum = pSum2[rpos];
      if (lpos > 0)
      { sum -= pSum2[lpos - 1]; }
      result = sum + (k - (rpos - lpos)) * maxVal;
      return result;
   }
   void resQuery(int len3, int arr3[], int sgT3[],
         int pSum3[], int q1[][3], int qlen1){
      int i;
      int result;
      for (i = 0; i < qlen1; i++) {
      result = solQuery(q1[i][0], q1[i][1],q1[i][2], len3, arr3, sgT3, pSum3);

      if (result == -1)
         { cout <<endl<<"Query "<<i+1<<": "<<"NO"; }
      else
         { cout <<endl<<"Query "<<i+1<<": "<<result; }
      }
   }
void preSum(int pSum4[], int arr4[], int len4){
   pSum4[0] = arr4[0];
   int j;
   for (j = 1; j < len4; j++){
      pSum4[j] = pSum4[j - 1] + arr4[j];
   }
}
int main(){
   int Arr[] = {1, 2, 4, -1 };
   int length = sizeof(Arr) / sizeof(Arr[0]);
   int sgTreee[5 * length];
   createTree(0, length - 1, 0, sgTreee, Arr, length);
   int pSum[length];
   preSum(pSum, Arr, length);
   int Q[][3] = { { 0, 2, 2 },
      { 0, 2, 1 },
      { 3, 3, 1 },
      { 0, 2, 3} };
   int qlen = sizeof(Q) / sizeof(Q[0]);
   resQuery(length, Arr, sgTreee, pSum, Q, qlen);
   return 0;
}

আউটপুট

যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে

Query 1: 7
Query 2: NO
Query 3: NO
Query 4: 11