समस्या कथन
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(sum और prefix_sum) संग्रहीत करता है, और अधिकतम उपसर्ग योग खोजने के लिए उस पर एक श्रेणी क्वेरी करें।
- अधिकतम उपसर्ग योग का पता लगाने के लिए, हमें दो चीजों की आवश्यकता होगी, एक योग और दूसरा उपसर्ग योग
- विलय दो चीजें लौटाएगा, श्रेणियों का योग और उपसर्ग योग जो सेगमेंट ट्री में अधिकतम (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