Dada una array de n números, la tarea es responder a las siguientes consultas:
maximumSubarraySum(start, end) : Find the maximum subarray sum in the range from array index 'start' to 'end'.
Ver también: Consulta de rango con ejemplos de actualización requerida :
Input : arr[] = {1, 3, -4, 5, -2}
Query 1: start = 0, end = 4
Query 2: start = 0, end = 2
Output : 5
4
Explanation:
For Query 1, [1, 3, -4, 5] or ( [5] )
represent the maximum sum sub arrays
with sum = 5.
For Query 2, [1, 3] represents the
maximum sum subarray in the query range
with sum = 4
Los árboles de segmentos se pueden usar para resolver este problema. Aquí, necesitamos mantener información sobre varias sumas acumulativas. En cada Node almacenamos lo siguiente:
1) Suma máxima de prefijos,
2) Suma máxima de sufijos,
3) Suma total,
4) Máxima Suma de subarreglo
Un árbol de segmento clásico con cada Node almacenando la información anterior debería ser suficiente para responder a cada consulta. El único enfoque aquí es cómo se fusionan los Nodes izquierdo y derecho del árbol. Ahora, discutiremos cómo se construye cada información en cada uno de los Nodes del árbol de segmentos utilizando la información de su hijo izquierdo y derecho.
Construcción de la suma máxima de prefijos usando los elementos secundarios izquierdo y derecho
Puede haber dos casos para la suma máxima de prefijos de un Node:
- La suma máxima de prefijos ocurre en el hijo izquierdo,
In this Case, Maximum Prefix Sum = Maximum Prefix Sum of Left Child
- La suma máxima de prefijos contiene todos los elementos de la array del hijo izquierdo y los elementos que contribuyen a la suma máxima de prefijos del hijo derecho,
In this Case,
Maximum Prefix Sum = Total Sum of Left Child +
Maximum Prefix Sum of Right Child
Construcción de la suma máxima de sufijos usando los elementos secundarios izquierdo y derecho
Puede haber dos casos para la suma máxima de sufijos de un Node:
- La suma máxima de sufijos ocurre en el hijo derecho,
In this Case, Maximum Suffix Sum = Maximum Suffix Sum of Right Child
- La suma máxima de sufijos contiene todos los elementos de la array del hijo derecho y los elementos que contribuyen a la suma máxima de sufijos del hijo izquierdo,
In this Case,
Maximum Suffix Sum = Total Sum of Right Child +
Maximum Suffix Sum of Left Child
Construyendo la suma máxima de subarreglo usando los elementos secundarios izquierdo y derecho
Puede haber tres casos para la suma máxima de subarreglo de un Node:
- La suma máxima de subarreglo se produce en el hijo izquierdo,
In this Case, Maximum Sub-array Sum = Maximum Subarray Sum of Left Child
- La suma máxima de subarreglo ocurre en el hijo derecho,
In this Case, Maximum Sub-array Sum = Maximum Subarray Sum of Right Child
- La suma máxima de subarreglo contiene elementos de array del hijo derecho que contribuyen a la suma máxima de prefijos del hijo derecho, y los elementos de array del hijo izquierdo que contribuyen a la suma máxima de sufijos del hijo izquierdo,
In this Case,
Maximum Subarray Sum = Maximum Prefix Sum of Right Child
+
Maximum Suffix Sum of Left Child
CPP
// C++ Program to Implement Maximum Sub-Array Sum in a range
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f
/* Node of the segment tree consisting of:
1. Maximum Prefix Sum,
2. Maximum Suffix Sum,
3. Total Sum,
4. Maximum Sub-Array Sum */
struct Node {
int maxPrefixSum;
int maxSuffixSum;
int totalSum;
int maxSubarraySum;
Node()
{
maxPrefixSum = maxSuffixSum = maxSubarraySum = -inf;
totalSum = -inf;
}
};
// Returns Parent Node after merging its left and right child
Node merge(Node leftChild, Node rightChild)
{
Node parentNode;
parentNode.maxPrefixSum = max(leftChild.maxPrefixSum,
leftChild.totalSum +
rightChild.maxPrefixSum);
parentNode.maxSuffixSum = max(rightChild.maxSuffixSum,
rightChild.totalSum +
leftChild.maxSuffixSum);
parentNode.totalSum = leftChild.totalSum +
rightChild.totalSum;
parentNode.maxSubarraySum = max({leftChild.maxSubarraySum,
rightChild.maxSubarraySum,
leftChild.maxSuffixSum +
rightChild.maxPrefixSum});
return parentNode;
}
// Builds the Segment tree recursively
void constructTreeUtil(Node* tree, int arr[], int start,
int end, int index)
{
/* Leaf Node */
if (start == end) {
// single element is covered under this range
tree[index].totalSum = arr[start];
tree[index].maxSuffixSum = arr[start];
tree[index].maxPrefixSum = arr[start];
tree[index].maxSubarraySum = arr[start];
return;
}
// Recursively Build left and right children
int mid = (start + end) / 2;
constructTreeUtil(tree, arr, start, mid, 2 * index);
constructTreeUtil(tree, arr, mid + 1, end, 2 * index + 1);
// Merge left and right child into the Parent Node
tree[index] = merge(tree[2 * index], tree[2 * index + 1]);
}
/* Function to construct segment tree from given array.
This function allocates memory for segment tree and
calls constructTreeUtil() to fill the allocated
memory */
Node* constructTree(int arr[], int n)
{
// Allocate memory for segment tree
int x = (int)(ceil(log2(n))); // Height of the tree
// Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
Node* tree = new Node[max_size];
// Fill the allocated memory tree
constructTreeUtil(tree, arr, 0, n - 1, 1);
// Return the constructed segment tree
return tree;
}
/* A Recursive function to get the desired
Maximum Sum Sub-Array,
The following are parameters of the function-
tree --> Pointer to segment tree
index --> Index of the segment tree Node
ss & se --> Starting and ending indexes of the
segment represented by
current Node, i.e., tree[index]
qs & qe --> Starting and ending indexes of query range */
Node queryUtil(Node* tree, int ss, int se, int qs,
int qe, int index)
{
// No overlap
if (ss > qe || se < qs) {
// returns a Node for out of bounds condition
Node nullNode;
return nullNode;
}
// Complete overlap
if (ss >= qs && se <= qe) {
return tree[index];
}
// Partial Overlap Merge results of Left
// and Right subtrees
int mid = (ss + se) / 2;
Node left = queryUtil(tree, ss, mid, qs, qe,
2 * index);
Node right = queryUtil(tree, mid + 1, se, qs,
qe, 2 * index + 1);
// merge left and right subtree query results
Node res = merge(left, right);
return res;
}
/* Returns the Maximum Subarray Sum between start and end
It mainly uses queryUtil(). */
int query(Node* tree, int start, int end, int n)
{
Node res = queryUtil(tree, 0, n - 1, start, end, 1);
return res.maxSubarraySum;
}
int main()
{
int arr[] = { 1, 3, -4, 5, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
// Construct Segment Tree
Node* Tree = constructTree(arr, n);
int start, end, maxSubarraySum;
// Answering query 1:
start = 0;
end = 4;
maxSubarraySum = query(Tree, start, end, n);
cout << "Maximum Sub-Array Sum between "
<< start << " and " << end
<< " = " << maxSubarraySum << "\n";
// Answering query 2:
start = 0;
end = 2;
maxSubarraySum = query(Tree, start, end, n);
cout << "Maximum Sub-Array Sum between "
<< start << " and " << end
<< " = " << maxSubarraySum << "\n";
return 0;
}
Producción:
Maximum Sub-Array Sum between 0 and 4 = 5 Maximum Sub-Array Sum between 0 and 2 = 4
Complejidad de tiempo: O (logn) para cada consulta.