Dada una array arr[] de longitud N, la tarea es encontrar la suma de los elementos máximos de cada subarreglo posible de la array.
Ejemplos:
Input : arr[] = {1, 3, 1, 7}
Output : 42
Max of all sub-arrays:
{1} - 1
{1, 3} - 3
{1, 3, 1} - 3
{1, 3, 1, 7} - 7
{3} - 3
{3, 1} - 3
{3, 1, 7} - 7
{1} - 1
{1, 7} - 7
{7} - 7
1 + 3 + 3 + 7 + 3 + 3 + 7 + 1 + 7 + 7 = 42
Input : arr[] = {1, 1, 1, 1, 1}
Output : 15
Ya hemos discutido un enfoque O(N) usando stack para este problema en este artículo .
Enfoque:
en este artículo, aprenderemos cómo resolver este problema usando divide y vencerás .
Supongamos que el elemento en el i -ésimo índice es el más grande de todos. Para cualquier subarreglo que contenga el índice ‘i’, el elemento en ‘i’ siempre será el máximo en el subarreglo.
Si el elemento en el i -ésimo índice es el más grande, podemos decir con seguridad que ese elemento en el i-ésimo índice será el más grande en los subarreglos (i+1)*(Ni). Entonces, su contribución total será arr[i]*(i+1)*(Ni). Ahora, dividiremos la array en dos partes, (0, i-1) y (i+1, N-1) y aplicaremos los mismos algoritmos a ambas por separado.
Entonces nuestra relación general de recurrencia será:
maxSumSubarray(arr, l, r) = arr[i]*(r-i+1)*(i-l+1)
+ maxSumSubarray(arr, l, i-1)
+ maxSumSubarray(arr, i+1, r)
where i is index of maximum element in range [l, r].
Ahora, necesitamos una forma de responder de manera eficiente a las consultas rangeMax(). El árbol de segmentos será una forma eficiente de responder a esta consulta. Tendremos que responder a esta consulta como máximo N veces. Por lo tanto, la complejidad temporal de nuestro algoritmo divide y vencerás será O(Nlog(N)).
Si tenemos que responder el problema «Suma del mínimo de todos los subarreglos», entonces usaremos el árbol de segmentos para responder las consultas rangeMin(). Para esto, puede pasar por el rango mínimo del árbol del segmento del artículo .
A continuación se muestra el código de implementación:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define seg_max 51
using namespace std;
// Array to store segment tree.
// In first we will store the maximum
// of a range
// In second, we will store index of
// that range
pair<int, int> seg_tree[seg_max];
// Size of array declared global
// to maintain simplicity in code
int n;
// Function to build segment tree
pair<int, int> buildMaxTree(int l, int r, int i, int arr[])
{
// Base case
if (l == r) {
seg_tree[i] = { arr[l], l };
return seg_tree[i];
}
// Finding the maximum among left and right child
seg_tree[i] = max(buildMaxTree(l, (l + r) / 2, 2 * i + 1, arr),
buildMaxTree((l + r) / 2 + 1, r, 2 * i + 2, arr));
// Returning the maximum to parent
return seg_tree[i];
}
// Function to perform range-max query in segment tree
pair<int, int> rangeMax(int l, int r, int arr[],
int i = 0, int sl = 0, int sr = n - 1)
{
// Base cases
if (sr < l || sl > r)
return { INT_MIN, -1 };
if (sl >= l and sr <= r)
return seg_tree[i];
// Finding the maximum among left and right child
return max(rangeMax(l, r, arr, 2 * i + 1, sl, (sl + sr) / 2),
rangeMax(l, r, arr, 2 * i + 2, (sl + sr) / 2 + 1, sr));
}
// Function to find maximum sum subarray
int maxSumSubarray(int arr[], int l = 0, int r = n - 1)
{
// base case
if (l > r)
return 0;
// range-max query to determine
// largest in the range.
pair<int, int> a = rangeMax(l, r, arr);
// divide the array in two parts
return a.first * (r - a.second + 1) * (a.second - l + 1)
+ maxSumSubarray(arr, l, a.second - 1)
+ maxSumSubarray(arr, a.second + 1, r);
}
// Driver Code
int main()
{
// Input array
int arr[] = { 1, 3, 1, 7 };
// Size of array
n = sizeof(arr) / sizeof(int);
// Builind the segment-tree
buildMaxTree(0, n - 1, 0, arr);
cout << maxSumSubarray(arr);
return 0;
}
Java
// Java implementation of the above approach
class GFG {
static class pair {
int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
static final int seg_max = 51;
// Array to store segment tree.
// In first we will store the maximum
// of a range
// In second, we will store index of
// that range
static pair[] seg_tree = new pair[seg_max];
// Size of array declared global
// to maintain simplicity in code
static int n;
// Function to build segment tree
static pair buildMaxTree(int l, int r, int i, int arr[])
{
// Base case
if (l == r) {
seg_tree[i] = new pair(arr[l], l);
return seg_tree[i];
}
// Finding the maximum among left and right child
seg_tree[i] = max(buildMaxTree(l, (l + r) / 2, 2 * i + 1, arr),
buildMaxTree((l + r) / 2 + 1, r, 2 * i + 2, arr));
// Returning the maximum to parent
return seg_tree[i];
}
// Function to perform range-max query in segment tree
static pair rangeMax(int l, int r, int arr[],
int i, int sl, int sr)
{
// Base cases
if (sr < l || sl > r)
return new pair(Integer.MIN_VALUE, -1);
if (sl >= l && sr <= r)
return seg_tree[i];
// Finding the maximum among left and right child
return max(rangeMax(l, r, arr, 2 * i + 1, sl, (sl + sr) / 2),
rangeMax(l, r, arr, 2 * i + 2, (sl + sr) / 2 + 1, sr));
}
static pair max(pair f, pair s) {
if (f.first > s.first)
return f;
else
return s;
}
// Function to find maximum sum subarray
static int maxSumSubarray(int arr[], int l, int r)
{
// base case
if (l > r)
return 0;
// range-max query to determine
// largest in the range.
pair a = rangeMax(l, r, arr, 0, 0, n - 1);
// divide the array in two parts
return a.first * (r - a.second + 1) * (a.second - l + 1)
+ maxSumSubarray(arr, l, a.second - 1)
+ maxSumSubarray(arr, a.second + 1, r);
}
// Driver Code
public static void main(String[] args)
{
// Input array
int arr[] = { 1, 3, 1, 7 };
// Size of array
n = arr.length;
// Builind the segment-tree
buildMaxTree(0, n - 1, 0, arr);
System.out.print(maxSumSubarray(arr, 0, n - 1));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach import sys seg_max = 51 # Array to store segment tree. # In first we will store the maximum # of a range # In second, we will store index of # that range seg_tree = [[] for i in range(seg_max)] # Function to build segment tree def buildMaxTree(l, r, i, arr): global n, seg_tree, seg_max # Base case if l == r: seg_tree[i] = [arr[l], l] return seg_tree[i] # Finding the maximum among left and right child seg_tree[i] = max(buildMaxTree(l, int((l + r) / 2), 2 * i + 1, arr), buildMaxTree(int((l + r) / 2) + 1, r, 2 * i + 2, arr)) # Returning the maximum to parent return seg_tree[i] # Function to perform range-max query in segment tree def rangeMax(l, r, arr, i, sl, sr): global n, seg_tree, seg_max # Base cases if sr < l or sl > r: return [-sys.maxsize, -1] if sl >= l and sr <= r: return seg_tree[i] # Finding the maximum among left and right child return max(rangeMax(l, r, arr, 2 * i + 1, sl, int((sl + sr) / 2)), rangeMax(l, r, arr, 2 * i + 2, int((sl + sr) / 2) + 1, sr)) def Max(f, s): if f[0] > s[0]: return f else: return s # Function to find maximum sum subarray def maxSumSubarray(arr, l, r): # base case if l > r: return 0 # range-max query to determine # largest in the range. a = rangeMax(l, r, arr, 0, 0, n - 1) # divide the array in two parts return a[0] * (r - a[1] + 1) * (a[1] - l + 1) + maxSumSubarray(arr, l, a[1] - 1) + maxSumSubarray(arr, a[1] + 1, r) # Input array arr = [ 1, 3, 1, 7 ] # Size of array n = len(arr) # Builind the segment-tree buildMaxTree(0, n - 1, 0, arr) print(maxSumSubarray(arr, 0, n - 1)) # This code is contributed by decode2207.
C#
// C# implementation of the above approach
using System;
class GFG {
class pair {
public int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
static readonly int seg_max = 51;
// Array to store segment tree.
// In first we will store the maximum
// of a range
// In second, we will store index of
// that range
static pair[] seg_tree = new pair[seg_max];
// Size of array declared global
// to maintain simplicity in code
static int n;
// Function to build segment tree
static pair buildMaxTree(int l, int r, int i, int []arr)
{
// Base case
if (l == r) {
seg_tree[i] = new pair(arr[l], l);
return seg_tree[i];
}
// Finding the maximum among left and right child
seg_tree[i] = max(buildMaxTree(l, (l + r) / 2, 2 * i + 1, arr),
buildMaxTree((l + r) / 2 + 1, r, 2 * i + 2, arr));
// Returning the maximum to parent
return seg_tree[i];
}
// Function to perform range-max query in segment tree
static pair rangeMax(int l, int r, int []arr,
int i, int sl, int sr)
{
// Base cases
if (sr < l || sl > r)
return new pair(int.MinValue, -1);
if (sl >= l && sr <= r)
return seg_tree[i];
// Finding the maximum among left and right child
return max(rangeMax(l, r, arr, 2 * i + 1, sl, (sl + sr) / 2),
rangeMax(l, r, arr, 2 * i + 2, (sl + sr) / 2 + 1, sr));
}
static pair max(pair f, pair s) {
if (f.first > s.first)
return f;
else
return s;
}
// Function to find maximum sum subarray
static int maxSumSubarray(int []arr, int l, int r)
{
// base case
if (l > r)
return 0;
// range-max query to determine
// largest in the range.
pair a = rangeMax(l, r, arr, 0, 0, n - 1);
// divide the array in two parts
return a.first * (r - a.second + 1) * (a.second - l + 1)
+ maxSumSubarray(arr, l, a.second - 1)
+ maxSumSubarray(arr, a.second + 1, r);
}
// Driver Code
public static void Main(String[] args)
{
// Input array
int []arr = { 1, 3, 1, 7 };
// Size of array
n = arr.Length;
// Builind the segment-tree
buildMaxTree(0, n - 1, 0, arr);
Console.Write(maxSumSubarray(arr, 0, n - 1));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of the above approach
class pair
{
constructor(first,second)
{
this.first = first;
this.second = second;
}
}
let seg_max = 51;
// Array to store segment tree.
// In first we will store the maximum
// of a range
// In second, we will store index of
// that range
let seg_tree = new Array(seg_max);
// Size of array declared global
// to maintain simplicity in code
let n;
// Function to build segment tree
function buildMaxTree(l,r,i,arr)
{
// Base case
if (l == r) {
seg_tree[i] = new pair(arr[l], l);
return seg_tree[i];
}
// Finding the maximum among left and right child
seg_tree[i] = max(buildMaxTree(l, Math.floor((l + r) / 2),
2 * i + 1, arr), buildMaxTree(Math.floor((l + r) / 2) +
1, r, 2 * i + 2, arr));
// Returning the maximum to parent
return seg_tree[i];
}
// Function to perform range-max query in segment tree
function rangeMax(l,r,arr,i,sl,sr)
{
// Base cases
if (sr < l || sl > r)
return new pair(Number.MIN_VALUE, -1);
if (sl >= l && sr <= r)
return seg_tree[i];
// Finding the maximum among left and right child
return max(rangeMax(l, r, arr, 2 * i + 1, sl,
Math.floor((sl + sr) / 2)),
rangeMax(l, r, arr, 2 * i + 2,
Math.floor((sl + sr) / 2) + 1, sr));
}
function max(f,s)
{
if (f.first > s.first)
return f;
else
return s;
}
// Function to find maximum sum subarray
function maxSumSubarray(arr,l,r)
{
// base case
if (l > r)
return 0;
// range-max query to determine
// largest in the range.
let a = rangeMax(l, r, arr, 0, 0, n - 1);
// divide the array in two parts
return a.first * (r - a.second + 1) * (a.second - l + 1)
+ maxSumSubarray(arr, l, a.second - 1)
+ maxSumSubarray(arr, a.second + 1, r);
}
// Driver Code
// Input array
let arr = [ 1, 3, 1, 7 ];
// Size of array
n = arr.length;
// Builind the segment-tree
buildMaxTree(0, n - 1, 0, arr);
document.write(maxSumSubarray(arr, 0, n - 1));
// This code is contributed by rag2127
</script>
Producción:
42
Complejidad del tiempo : O(Nlog(N))
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA