C++ এ একটি প্রদত্ত পরিসরের জন্য সর্বাধিক উপসর্গ-সমষ্টি

সমস্যা বিবৃতি

n পূর্ণসংখ্যা এবং q প্রশ্নগুলির একটি অ্যারে দেওয়া, প্রতিটি প্রশ্নের l থেকে r পর্যন্ত পরিসীমা রয়েছে। l – r.

উদাহরণ

If input array is arr[] = {-1, 2, 3, -5} and
queries = 2 and ranges are:
l = 0, r = 3
l = 1, r = 3 then output will be 4 and 5.

• প্রথম কোয়েরির পরিসরে (0, 3) [-1, 2, 3, -5] আছে, যেহেতু এটি উপসর্গ, তাই আমাদের -1 থেকে শুরু করতে হবে। তাই, সর্বোচ্চ উপসর্গ যোগফল হবে -1 + 2 + 3 =4
• দ্বিতীয় কোয়েরির পরিসরে (1, 3) [2, 3, -5] আছে, যেহেতু এটি উপসর্গ, তাই আমাদের 2 থেকে শুরু করতে হবে। তাই, সর্বাধিক উপসর্গ যোগফল হবে 2 + 3 =5<

অ্যালগরিদম

• একটি সেগমেন্ট ট্রি তৈরি করুন যেখানে প্রতিটি নোড দুটি মান s(সমষ্টি এবং উপসর্গ_সম) সঞ্চয় করে, এবং সর্বাধিক উপসর্গ যোগফল খুঁজে পেতে এটিতে একটি পরিসর কোয়েরি করুন।
• সর্বোচ্চ উপসর্গ যোগফল বের করার জন্য, আমাদের দুটি জিনিসের প্রয়োজন হবে, একটি হল সমষ্টি এবং অন্যটি উপসর্গ যোগফল
• একত্রীকরণ দুটি জিনিস ফিরিয়ে দেবে, ব্যাপ্তির যোগফল এবং উপসর্গের যোগফল যা সর্বোচ্চ (prefix.left, prefix.sum + prefix.right) সেগমেন্ট ট্রিগুলিতে সংরক্ষণ করবে
• যেকোন দুটি পরিসরের সমন্বয়ের জন্য সর্বাধিক উপসর্গ যোগফল হবে বাম দিক থেকে উপসর্গের যোগফল অথবা বাম পাশের যোগফল + ডান পাশের উপসর্গের যোগফল, যেটি সর্বাধিক বিবেচনা করা হয়।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef struct node {
   int sum;
   int prefix;
} node;
node tree[4 * 10000];
void build(int *arr, int idx, int start, int end) {
   if (start == end) {
      tree[idx].sum = arr[start];
      tree[idx].prefix = arr[start];
   } else {
      int mid = (start + end) / 2;
      build(arr, 2 * idx + 1, start, mid);
      build(arr, 2 * idx + 2, mid + 1, end);
      tree[idx].sum = tree[2 * idx + 1].sum + tree[2 *
      idx + 2].sum;
      tree[idx].prefix = max(tree[2 * idx + 1].prefix,
      tree[2 * idx + 1].sum + tree[2 * idx + 2].prefix);
   }
}
node query(int idx, int start, int end, int l, int r) {
   node result;
   result.sum = result.prefix = -1;
   if (start > r || end < l) {
      return result;
   }
   if (start >= l && end <= r) {
      return tree[idx];
   }
   int mid = (start + end) / 2;
   if (l > mid) {
      return query(2 * idx + 2, mid + 1, end, l, r);
   }
   if (r <= mid) {
      return query(2 * idx + 1, start, mid, l, r);
   }
   node left = query(2 * idx + 1, start, mid, l, r);
   node right = query(2 * idx + 2, mid + 1, end, l, r);
   result.sum = left.sum + right.sum;
   result.prefix = max(left.prefix, left.sum + right.prefix);
   return result;
}
int main() {
   int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
   int n = sizeof(arr) / sizeof(arr[0]);
   build(arr, 0, 0, n - 1);
   cout << "Result = " << query(0, 0, n - 1, 3, 5).prefix
   << endl;
   return 0;
}

আউটপুট

যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −

Result = -1