Dado un arreglo arr[] , la tarea es encontrar los elementos de un subarreglo contiguo de números que tiene la suma más grande.
Ejemplos:
Entrada: arr = [-2, -3, 4, -1, -2, 1, 5, -3]
Salida: [4, -1, -2, 1, 5]
Explicación:
En la entrada anterior, el máximo contiguo la suma del subarreglo es 7 y los elementos del subarreglo son [4, -1, -2, 1, 5]Entrada: arr = [-2, -5, 6, -2, -3, 1, 5, -6]
Salida: [6, -2, -3, 1, 5]
Explicación:
En la entrada anterior, el máximo contiguo la suma del subarreglo es 7 y los elementos
del subarreglo son [6, -2, -3, 1, 5]
Enfoque ingenuo: El enfoque ingenuo es generar todo el subarreglo posible e imprimir ese subarreglo que tiene la suma máxima.
Complejidad temporal: O(N 2 )
Espacio auxiliar: O(1)
Enfoque eficiente: la idea es utilizar el algoritmo de Kadane para encontrar la suma máxima del subarreglo y almacenar el índice inicial y final del subarreglo que tiene la suma máxima e imprimir el subarreglo desde el índice inicial hasta el índice final. A continuación se muestran los pasos:
- Inicialice 3 variables endIndex a 0, currMax y globalMax al primer valor de la array de entrada.
- Para cada elemento de la array a partir de index(digamos i ) 1, actualice currMax a max(nums[i], nums[i] + currMax) y globalMax y endIndex a i solo si currMax > globalMax .
- Para encontrar el índice de inicio, itere desde endIndex en la dirección izquierda y siga disminuyendo el valor de globalMax hasta que se convierta en 0. El punto en el que se convierte en 0 es el índice de inicio.
- Ahora imprima el subarreglo entre [start, end] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the elements
// of Subarray with maximum sum
void SubarrayWithMaxSum(vector<int>& nums)
{
// Initialize currMax and globalMax
// with first value of nums
int endIndex, currMax = nums[0];
int globalMax = nums[0];
// Iterate for all the elements
// of the array
for (int i = 1; i < nums.size(); ++i) {
// Update currMax
currMax = max(nums[i],
nums[i] + currMax);
// Check if currMax is greater
// than globalMax
if (currMax > globalMax) {
globalMax = currMax;
endIndex = i;
}
}
int startIndex = endIndex;
// Traverse in left direction to
// find start Index of subarray
while (startIndex >= 0) {
globalMax -= nums[startIndex];
if (globalMax == 0)
break;
// Decrement the start index
startIndex--;
}
// Printing the elements of
// subarray with max sum
for (int i = startIndex;
i <= endIndex; ++i) {
cout << nums[i] << " ";
}
}
// Driver Code
int main()
{
// Given array arr[]
vector<int> arr
= { -2, -5, 6, -2,
-3, 1, 5, -6 };
// Function call
SubarrayWithMaxSum(arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print the elements
// of Subarray with maximum sum
static void SubarrayWithMaxSum(Vector<Integer> nums)
{
// Initialize currMax and globalMax
// with first value of nums
int endIndex = 0, currMax = nums.get(0);
int globalMax = nums.get(0);
// Iterate for all the elements
// of the array
for (int i = 1; i < nums.size(); ++i)
{
// Update currMax
currMax = Math.max(nums.get(i),
nums.get(i) + currMax);
// Check if currMax is greater
// than globalMax
if (currMax > globalMax)
{
globalMax = currMax;
endIndex = i;
}
}
int startIndex = endIndex;
// Traverse in left direction to
// find start Index of subarray
while (startIndex >= 0)
{
globalMax -= nums.get(startIndex);
if (globalMax == 0)
break;
// Decrement the start index
startIndex--;
}
// Printing the elements of
// subarray with max sum
for(int i = startIndex; i <= endIndex; ++i)
{
System.out.print(nums.get(i) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
Vector<Integer> arr = new Vector<Integer>();
arr.add(-2);
arr.add(-5);
arr.add(6);
arr.add(-2);
arr.add(-3);
arr.add(1);
arr.add(5);
arr.add(-6);
// Function call
SubarrayWithMaxSum(arr);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach # Function to print the elements # of Subarray with maximum sum def SubarrayWithMaxSum(nums): # Initialize currMax and globalMax # with first value of nums currMax = nums[0] globalMax = nums[0] # Iterate for all the elements # of the array for i in range(1, len(nums)): # Update currMax currMax = max(nums[i], nums[i] + currMax) # Check if currMax is greater # than globalMax if (currMax > globalMax): globalMax = currMax endIndex = i startIndex = endIndex # Traverse in left direction to # find start Index of subarray while (startIndex >= 0): globalMax -= nums[startIndex] if (globalMax == 0): break # Decrement the start index startIndex -= 1 # Printing the elements of # subarray with max sum for i in range(startIndex, endIndex + 1): print(nums[i], end = " ") # Driver Code # Given array arr[] arr = [ -2, -5, 6, -2, -3, 1, 5, -6 ] # Function call SubarrayWithMaxSum(arr) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print the elements
// of Subarray with maximum sum
static void SubarrayWithMaxSum(List<int> nums)
{
// Initialize currMax and globalMax
// with first value of nums
int endIndex = 0, currMax = nums[0];
int globalMax = nums[0];
// Iterate for all the elements
// of the array
for (int i = 1; i < nums.Count; ++i)
{
// Update currMax
currMax = Math.Max(nums[i],
nums[i] + currMax);
// Check if currMax is greater
// than globalMax
if (currMax > globalMax)
{
globalMax = currMax;
endIndex = i;
}
}
int startIndex = endIndex;
// Traverse in left direction to
// find start Index of subarray
while (startIndex >= 0)
{
globalMax -= nums[startIndex];
if (globalMax == 0)
break;
// Decrement the start index
startIndex--;
}
// Printing the elements of
// subarray with max sum
for(int i = startIndex; i <= endIndex; ++i)
{
Console.Write(nums[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
List<int> arr = new List<int>();
arr.Add(-2);
arr.Add(-5);
arr.Add(6);
arr.Add(-2);
arr.Add(-3);
arr.Add(1);
arr.Add(5);
arr.Add(-6);
// Function call
SubarrayWithMaxSum(arr);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to print the elements
// of Subarray with maximum sum
function SubarrayWithMaxSum(nums)
{
// Initialize currMax and globalMax
// with first value of nums
var endIndex, currMax = nums[0];
var globalMax = nums[0];
// Iterate for all the elements
// of the array
for(var i = 1; i < nums.length; ++i)
{
// Update currMax
currMax = Math.max(nums[i],
nums[i] + currMax);
// Check if currMax is greater
// than globalMax
if (currMax > globalMax)
{
globalMax = currMax;
endIndex = i;
}
}
var startIndex = endIndex;
// Traverse in left direction to
// find start Index of subarray
while (startIndex >= 0)
{
globalMax -= nums[startIndex];
if (globalMax == 0)
break;
// Decrement the start index
startIndex--;
}
// Printing the elements of
// subarray with max sum
for(var i = startIndex;
i <= endIndex; ++i)
{
document.write(nums[i] + " ");
}
}
// Driver Code
// Given array arr[]
var arr = [ -2, -5, 6, -2,
-3, 1, 5, -6 ];
// Function call
SubarrayWithMaxSum(arr);
// This code is contributed by rutvik_56
</script>
Producción
6 -2 -3 1 5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente alternativo : este enfoque elimina el ciclo while interno que se mueve en la dirección izquierda y reduce global_max en el método mencionado anteriormente. Por lo tanto, este método reduce el tiempo.
- Inicialice currMax y globalMax al primer valor de la array de entrada. Inicialice endIndex, startIndex, globalMaxStartIndex a 0. (endIndex, startIndex almacenan los índices de inicio y final de la subarray de suma máxima que termina en i. globalMaxStartIndex almacena el índice de inicio de globalMax)
- Para cada elemento de la array a partir del índice (por ejemplo, i) 1, actualice currMax y startIndex a i si nums[i] > nums[i] + currMax. De lo contrario, solo actualice currMax.
- Actualice globalMax si currMax>globalMax. También actualice globalMaxStartIndex.
- Ahora imprima el subarreglo entre [start index, globalMaxStartIndex].
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to print the elements
// of Subarray with maximum sum
static void SubarrayWithMaxSum(Vector<Integer> nums)
{
// Initialize currMax and globalMax
// with first value of nums
int currMax = nums.get(0), globalMax = nums.get(0);
// Initialize endIndex startIndex,globalStartIndex
int endIndex = 0;
int startIndex = 0, globalMaxStartIndex = 0;
// Iterate for all the elements of the array
for (int i = 1; i < nums.size(); ++i) {
// Update currMax and startIndex
if (nums.get(i) > nums.get(i) + currMax) {
currMax = nums.get(i);
startIndex = i; // update the new startIndex
}
// Update currMax
else if (nums.get(i) < nums.get(i) + currMax) {
currMax = nums.get(i) + currMax;
}
// Update globalMax and globalMaxStartIndex
if (currMax > globalMax) {
globalMax = currMax;
endIndex = i;
globalMaxStartIndex = startIndex;
}
}
// Printing the elements of subarray with max sum
for (int i = globalMaxStartIndex; i <= endIndex;
++i) {
System.out.print(nums.get(i) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
Vector<Integer> arr = new Vector<Integer>();
arr.add(-2);
arr.add(-5);
arr.add(6);
arr.add(-2);
arr.add(-3);
arr.add(1);
arr.add(5);
arr.add(-6);
// Function call
SubarrayWithMaxSum(arr);
}
}
// This code is contributed by Amritha Basavaraj Patil
Python3
# Python program for the above approach: # Function to print the elements # of Subarray with maximum sum def SubarrayWithMaxSum(nums): # Initialize currMax and globalMax # with first value of nums currMax = nums[0] globalMax = nums[0] # Initialize endIndex startIndex,globalStartIndex endIndex = 0 startIndex = 0 globalMaxStartIndex = 0 # Iterate for all the elements of the array for i in range(1, len(nums)): # Update currMax and startIndex if (nums[i] > nums[i] + currMax): currMax = nums[i] startIndex = i # update the new startIndex # Update currMax elif (nums[i] < nums[i] + currMax): currMax += nums[i] # Update globalMax and globalMaxStartIndex if (currMax > globalMax): globalMax = currMax endIndex = i globalMaxStartIndex = startIndex # Printing the elements of subarray with max sum for i in range(globalMaxStartIndex, endIndex + 1): print(nums[i], end = ' ') ## Driver code if __name__=='__main__': # Given array arr[] arr = [] arr.append(-2) arr.append(-5) arr.append(6) arr.append(-2) arr.append(-3) arr.append(1) arr.append(5) arr.append(-6) # Function call SubarrayWithMaxSum(arr) # This code is contributed by subhamgoyal2014.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to print the elements
// of Subarray with maximum sum
static void SubarrayWithMaxSum(List<int> nums)
{
// Initialize currMax and globalMax
// with first value of nums
int currMax = nums[0], globalMax = nums[0];
// Initialize endIndex startIndex,globalStartIndex
int endIndex = 0;
int startIndex = 0, globalMaxStartIndex = 0;
// Iterate for all the elements of the array
for (int i = 1; i < nums.Count; ++i) {
// Update currMax and startIndex
if (nums[i] > nums[i] + currMax) {
currMax = nums[i];
startIndex = i; // update the new startIndex
}
// Update currMax
else if (nums[i] < nums[i] + currMax) {
currMax = nums[i] + currMax;
}
// Update globalMax and globalMaxStartIndex
if (currMax > globalMax) {
globalMax = currMax;
endIndex = i;
globalMaxStartIndex = startIndex;
}
}
// Printing the elements of subarray with max sum
for (int i = globalMaxStartIndex; i <= endIndex;
++i) {
Console.Write(nums[i] + " ");
}
}
// Driver Code
static public void Main (){
// Given array arr[]
List<int> arr = new List<int>();
arr.Add(-2);
arr.Add(-5);
arr.Add(6);
arr.Add(-2);
arr.Add(-3);
arr.Add(1);
arr.Add(5);
arr.Add(-6);
// Function call
SubarrayWithMaxSum(arr);
}
}
// This code is contributed by rag2127.
Javascript
<script>
// JavaScript program for the above approach
// Function to print the elements
// of Subarray with maximum sum
function SubarrayWithMaxSum(nums)
{
// Initialize currMax and globalMax
// with first value of nums
let currMax = nums[0], globalMax = nums[0];
// Initialize endIndex startIndex,globalStartIndex
let endIndex = 0;
let startIndex = 0, globalMaxStartIndex = 0;
// Iterate for all the elements of the array
for (let i = 1; i < nums.length; ++i) {
// Update currMax and startIndex
if (nums[i] > nums[i] + currMax) {
currMax = nums[i];
startIndex = i; // update the new startIndex
}
// Update currMax
else if (nums[i] < nums[i] + currMax) {
currMax = nums[i] + currMax;
}
// Update globalMax and globalMaxStartIndex
if (currMax > globalMax) {
globalMax = currMax;
endIndex = i;
globalMaxStartIndex = startIndex;
}
}
// Printing the elements of subarray with max sum
for (let i = globalMaxStartIndex; i <= endIndex;
++i) {
document.write(nums[i] + " ");
}
}
// Driver Code
let arr = [];
arr.push(-2);
arr.push(-5);
arr.push(6);
arr.push(-2);
arr.push(-3);
arr.push(1);
arr.push(5);
arr.push(-6);
// Function call
SubarrayWithMaxSum(arr);
// This code is contributed by unknown2108
</script>
Producción
6 -2 -3 1 5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por chirags_30 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA