Dado un arreglo arr[] de enteros, la tarea es encontrar el subarreglo de suma máxima entre todos los subarreglos posibles.
Ejemplos:
Entrada: arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Salida: 6
{4, -1, 2, 1} es el subarreglo requerido.
Entrada: arr[] = {2, 2, -2}
Salida: 4
Enfoque: Hasta ahora solo conocemos el Algoritmo de Kadane que resuelve este problema en O(n) usando programación dinámica.
También habíamos discutido un enfoque de divide y vencerás para el subarreglo de suma máxima en complejidad de tiempo O (N * logN).
El siguiente enfoque lo resuelve usando el enfoque Divide and Conquer que toma la misma complejidad de tiempo de O(n).
Los algoritmos de divide y vencerás generalmente implican dividir el problema en subproblemas y conquistarlos por separado. Para este problema mantenemos una estructura (en cpp) o clase (en java o python) que almacena los siguientes valores:
- Suma total de un subarreglo.
- Suma máxima de prefijos para un subarreglo.
- Suma máxima de sufijos para un subarreglo.
- Suma máxima general para un subconjunto. (Esto contiene la suma máxima para un subconjunto).
Durante la recursión (Dividir parte), la array se divide en 2 partes desde el medio. La estructura del Node izquierdo contiene todos los valores anteriores para la parte izquierda de la array y la estructura del Node derecho contiene todos los valores anteriores. Teniendo ambos Nodes, ahora podemos fusionar los dos Nodes calculando todos los valores para el Node resultante.
La suma máxima de prefijos para el Node resultante será el valor máximo entre la suma máxima de prefijos del Node izquierdo o la suma del Node izquierdo + la suma máxima de prefijos del Node derecho o la suma total de ambos Nodes (lo cual es posible para una array con todos los valores positivos) .
De manera similar, la suma máxima de sufijos para el Node resultante será el valor máximo entre la suma máxima de sufijos del Node derecho o la suma del Node derecho + la suma máxima de sufijos del Node izquierdo o la suma total de ambos Nodes (lo que nuevamente es posible para una array con todos los positivos). valores).
La suma total del Node resultante es la suma de la suma del Node izquierdo y del Node derecho.
Ahora, la suma máxima del subarreglo para el Node resultante será máxima entre la suma del prefijo del Node resultante, la suma del sufijo del Node resultante, la suma total del Node resultante, la suma máxima del Node izquierdo, la suma máxima del Node derecho, la suma de la suma máxima del sufijo de Node izquierdo y suma máxima de prefijos del Node derecho.
Aquí, la parte de conquista se puede realizar en tiempo O(1) combinando el resultado de las estructuras de los Nodes izquierdo y derecho.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
struct Node {
// To store the maximum sum
// for a sub-array
long long _max;
// To store the maximum prefix
// sum for a sub-array
long long _pre;
// To store the maximum suffix
// sum for a sub-array
long long _suf;
// To store the total sum
// for a sub-array
long long _sum;
};
// Function to create a node
Node getNode(long long x){
Node a;
a._max = x;
a._pre = x;
a._suf = x;
a._sum = x;
return a;
}
// Function to merge the 2 nodes left and right
Node merg(const Node &l, const Node &r){
// Creating node ans
Node ans ;
// Initializing all the variables:
ans._max = ans._pre = ans._suf = ans._sum = 0;
// The max prefix sum of ans Node is maximum of
// a) max prefix sum of left Node
// b) sum of left Node + max prefix sum of right Node
// c) sum of left Node + sum of right Node
ans._pre = max({l._pre, l._sum+r._pre, l._sum+r._sum});
// The max suffix sum of ans Node is maximum of
// a) max suffix sum of right Node
// b) sum of right Node + max suffix sum of left Node
// c) sum of left Node + sum of right Node
ans._suf = max({r._suf, r._sum+l._suf, l._sum+r._sum});
// Total sum of ans Node = total sum of left Node + total sum of right Node
ans._sum = l._sum + r._sum;
// The max sum of ans Node stores the answer which is the maximum value among:
// prefix sum of ans Node
// suffix sum of ans Node
// maximum value of left Node
// maximum value of right Node
// prefix value of right Node + suffix value of left Node
ans._max = max({ans._pre, ans._suf, ans._sum,l._max, r._max, l._suf+r._pre});
// Return the ans Node
return ans;
}
// Function for calculating the
// max_sum_subArray using divide and conquer
Node getMaxSumSubArray(int l, int r, vector<long long> &ar){
if (l == r) return getNode(ar[l]);
int mid = (l + r) >> 1;
// Call method to return left Node:
Node left = getMaxSumSubArray(l, mid, ar);
// Call method to return right Node:
Node right = getMaxSumSubArray(mid+1, r, ar);
// Return the merged Node:
return merg(left, right);
}
// Driver code
int main(){
vector<long long> ar = {-2, -5, 6, -2, -3, 1, 5, -6};
int n = ar.size();
Node ans = getMaxSumSubArray(0, n-1, ar);
cout << "Answer is " << ans._max << "\n";
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static class Node
{
// To store the maximum sum
// for a sub-array
int _max;
// To store the maximum prefix
// sum for a sub-array
int _pre;
// To store the maximum suffix
// sum for a sub-array
int _suf;
// To store the total sum
// for a sub-array
int _sum;
};
// Function to create a node
static Node getNode(int x)
{
Node a = new Node();
a._max = x;
a._pre = x;
a._suf = x;
a._sum = x;
return a;
}
// Function to merge the 2 nodes left and right
static Node merg(Node l, Node r)
{
// Creating node ans
Node ans = new Node();
// Initializing all the variables:
ans._max = ans._pre = ans._suf = ans._sum = 0;
// The max prefix sum of ans Node is maximum of
// a) max prefix sum of left Node
// b) sum of left Node + max prefix sum of right Node
// c) sum of left Node + sum of right Node
ans._pre = Arrays.stream(new int[]{l._pre, l._sum+r._pre,
l._sum+r._sum}).max().getAsInt();
// The max suffix sum of ans Node is maximum of
// a) max suffix sum of right Node
// b) sum of right Node + max suffix sum of left Node
// c) sum of left Node + sum of right Node
ans._suf = Arrays.stream(new int[]{r._suf, r._sum+l._suf,
l._sum+r._sum}).max().getAsInt();
// Total sum of ans Node = total sum of
// left Node + total sum of right Node
ans._sum = l._sum + r._sum;
// The max sum of ans Node stores
// the answer which is the maximum value among:
// prefix sum of ans Node
// suffix sum of ans Node
// maximum value of left Node
// maximum value of right Node
// prefix value of right Node + suffix value of left Node
ans._max = Arrays.stream(new int[]{ans._pre,
ans._suf,
ans._sum,
l._max, r._max,
l._suf+r._pre}).max().getAsInt();
// Return the ans Node
return ans;
}
// Function for calculating the
// max_sum_subArray using divide and conquer
static Node getMaxSumSubArray(int l, int r, int []ar)
{
if (l == r) return getNode(ar[l]);
int mid = (l + r) >> 1;
// Call method to return left Node:
Node left = getMaxSumSubArray(l, mid, ar);
// Call method to return right Node:
Node right = getMaxSumSubArray(mid + 1, r, ar);
// Return the merged Node:
return merg(left, right);
}
// Driver code
public static void main(String[] args)
{
int []ar = {-2, -5, 6, -2, -3, 1, 5, -6};
int n = ar.length;
Node ans = getMaxSumSubArray(0, n - 1, ar);
System.out.print("Answer is " + ans._max + "\n");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 implementation of the approach
class Node:
def __init__(self, x):
# To store the maximum sum for a sub-array
self._max = x
# To store the maximum prefix sum for a sub-array
self._pre = x
# To store the maximum suffix sum for a sub-array
self._suf = x
# To store the total sum for a sub-array
self._sum = x
# Function to merge the 2 nodes left and right
def merg(l, r):
# Creating node ans
ans = Node(0)
# The max prefix sum of ans Node is maximum of
# a) max prefix sum of left Node
# b) sum of left Node + max prefix sum of right Node
# c) sum of left Node + sum of right Node
ans._pre = max(l._pre, l._sum+r._pre, l._sum+r._sum)
# The max suffix sum of ans Node is maximum of
# a) max suffix sum of right Node
# b) sum of right Node + max suffix sum of left Node
# c) sum of left Node + sum of right Node
ans._suf = max(r._suf, r._sum+l._suf, l._sum+r._sum)
# Total sum of ans Node = total sum of
# left Node + total sum of right Node
ans._sum = l._sum + r._sum
# The max sum of ans Node stores the answer
# which is the maximum value among:
# prefix sum of ans Node
# suffix sum of ans Node
# maximum value of left Node
# maximum value of right Node
# prefix value of left Node + suffix value of right Node
ans._max = max(ans._pre, ans._suf, ans._sum,
l._max, r._max, l._suf+r._pre)
# Return the ans Node
return ans
# Function for calculating the
# max_sum_subArray using divide and conquer
def getMaxSumSubArray(l, r, ar):
if l == r: return Node(ar[l])
mid = (l + r) // 2
# Call method to return left Node:
left = getMaxSumSubArray(l, mid, ar)
# Call method to return right Node:
right = getMaxSumSubArray(mid+1, r, ar)
# Return the merged Node:
return merg(left, right)
# Driver code
if __name__ == "__main__":
ar = [-2, -5, 6, -2, -3, 1, 5, -6]
n = len(ar)
ans = getMaxSumSubArray(0, n-1, ar)
print("Answer is", ans._max)
# This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Linq;
public class GFG
{
class Node
{
// To store the maximum sum
// for a sub-array
public int _max;
// To store the maximum prefix
// sum for a sub-array
public int _pre;
// To store the maximum suffix
// sum for a sub-array
public int _suf;
// To store the total sum
// for a sub-array
public int _sum;
};
// Function to create a node
static Node getNode(int x)
{
Node a = new Node();
a._max = x;
a._pre = x;
a._suf = x;
a._sum = x;
return a;
}
// Function to merge the 2 nodes left and right
static Node merg(Node l, Node r)
{
// Creating node ans
Node ans = new Node();
// Initializing all the variables:
ans._max = ans._pre = ans._suf = ans._sum = 0;
// The max prefix sum of ans Node is maximum of
// a) max prefix sum of left Node
// b) sum of left Node + max prefix sum of right Node
// c) sum of left Node + sum of right Node
ans._pre = (new int[]{l._pre, l._sum+r._pre,
l._sum+r._sum}).Max();
// The max suffix sum of ans Node is maximum of
// a) max suffix sum of right Node
// b) sum of right Node + max suffix sum of left Node
// c) sum of left Node + sum of right Node
ans._suf = (new int[]{r._suf, r._sum+l._suf,
l._sum+r._sum}).Max();
// Total sum of ans Node = total sum of
// left Node + total sum of right Node
ans._sum = l._sum + r._sum;
// The max sum of ans Node stores
// the answer which is the maximum value among:
// prefix sum of ans Node
// suffix sum of ans Node
// maximum value of left Node
// maximum value of right Node
// prefix value of right Node + suffix value of left Node
ans._max = (new int[]{ans._pre,
ans._suf,
ans._sum,
l._max, r._max,
l._suf+r._pre}).Max();
// Return the ans Node
return ans;
}
// Function for calculating the
// max_sum_subArray using divide and conquer
static Node getMaxSumSubArray(int l, int r, int []ar)
{
if (l == r) return getNode(ar[l]);
int mid = (l + r) >> 1;
// Call method to return left Node:
Node left = getMaxSumSubArray(l, mid, ar);
// Call method to return right Node:
Node right = getMaxSumSubArray(mid + 1, r, ar);
// Return the merged Node:
return merg(left, right);
}
// Driver code
public static void Main(String[] args)
{
int []ar = {-2, -5, 6, -2, -3, 1, 5, -6};
int n = ar.Length;
Node ans = getMaxSumSubArray(0, n - 1, ar);
Console.Write("Answer is " + ans._max + "\n");
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation of the approach
class Node {
constructor()
{
// To store the maximum sum
// for a sub-array
var _max;
// To store the maximum prefix
// sum for a sub-array
var _pre;
// To store the maximum suffix
// sum for a sub-array
var _suf;
// To store the total sum
// for a sub-array
var _sum;
}
};
// Function to create a node
function getNode(x){
var a = new Node();
a._max = x;
a._pre = x;
a._suf = x;
a._sum = x;
return a;
}
// Function to merge the 2 nodes left and right
function merg(l, r){
// Creating node ans
var ans = new Node();
// Initializing all the variables:
ans._max = ans._pre = ans._suf = ans._sum = 0;
// The max prefix sum of ans Node is maximum of
// a) max prefix sum of left Node
// b) sum of left Node + max prefix sum of right Node
// c) sum of left Node + sum of right Node
ans._pre = Math.max(l._pre, l._sum+r._pre, l._sum+r._sum);
// The max suffix sum of ans Node is maximum of
// a) max suffix sum of right Node
// b) sum of right Node + max suffix sum of left Node
// c) sum of left Node + sum of right Node
ans._suf = Math.max(r._suf, r._sum+l._suf, l._sum+r._sum);
// Total sum of ans Node = total sum of left Node + total sum of right Node
ans._sum = l._sum + r._sum;
// The max sum of ans Node stores the answer which is the maximum value among:
// prefix sum of ans Node
// suffix sum of ans Node
// maximum value of left Node
// maximum value of right Node
// prefix value of right Node + suffix value of left Node
ans._max = Math.max(ans._pre, ans._suf, ans._sum,l._max, r._max, l._suf+r._pre);
// Return the ans Node
return ans;
}
// Function for calculating the
// max_sum_subArray using divide and conquer
function getMaxSumSubArray(l, r, ar){
if (l == r) return getNode(ar[l]);
var mid = (l + r) >> 1;
// Call method to return left Node:
var left = getMaxSumSubArray(l, mid, ar);
// Call method to return right Node:
var right = getMaxSumSubArray(mid+1, r, ar);
// Return the merged Node:
return merg(left, right);
}
// Driver code
var ar = [-2, -5, 6, -2, -3, 1, 5, -6];
var n = ar.length;
var ans = getMaxSumSubArray(0, n-1, ar);
document.write("Answer is " + ans._max + "<br>");
// This code is contributed by rutvik_56.
</script>
Producción:
Answer is 7
Complejidad de tiempo: la función recursiva getMaxSumSubArray() genera la siguiente relación de recurrencia.
T(n) = 2 * T(n / 2) + O(1) tenga en cuenta que conquistar parte solo toma O(1) tiempo. Entonces, al resolver esta recurrencia usando el Teorema de Master, obtenemos la complejidad temporal de O(n).
Publicación traducida automáticamente
Artículo escrito por Abhimanyu_97 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA