Dada una array arr[] de tamaño N, la tarea es encontrar la suma mínima de subarreglo en los subarreglos [i, N-1] para todo i en [0, N-1].
Ejemplos:
Entrada: arr[ ] = {3, -1, -2}
Salida: -3 -3 -2
Explicación:
Para (i = 1) es decir, {3, -1, -2}, la suma mínima del subarreglo es -3 para {-1, -2}.
Para (i = 2), es decir, {-1, -2}, la suma mínima del subarreglo es -3 para {-1, -2}.
Para (i = 3), es decir, {-2}, la suma mínima del subarreglo es -2 para {-2}.Entrada: arr[ ] = {5, -3, -2, 9, 4}
Salida: -5 -5 -2 4 4
Enfoque: el problema se puede resolver utilizando el algoritmo estándar de Kadane para la suma máxima de subarreglo . Siga los pasos a continuación para resolver este problema:
- Invierta los elementos de la array arr[], es decir, cambie números positivos a negativos y viceversa.
- Iterar en el rango [0, N-1] usando la variable i :
- Encuentre la suma máxima de subarreglo para subarreglo arr[i, N-1] usando el algoritmo de Kadane .
- Invierta el resultado nuevamente e imprima el resultado .
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;
// Kadane's Algorithm to find max
// sum subarray
int kadane(int arr[], int start, int end)
{
int currMax = arr[start];
int maxSoFar = arr[start];
// Iterating from start to end
for (int i = start + 1; i < end + 1; i++) {
currMax = max(arr[i], arr[i] + currMax);
maxSoFar = max(maxSoFar, currMax);
}
// Returning maximum sum
return maxSoFar;
}
// Function to find the minimum subarray
// sum for each suffix
void minSubarraySum(int arr[], int n)
{
// Inverting all the elements of
// array arr[].
for (int i = 0; i < n; i++) {
arr[i] = -arr[i];
}
// Finding the result for each
// subarray
for (int i = 0; i < n; i++) {
// Finding the max subarray sum
int result = kadane(arr, i, n - 1);
// Inverting the result
result = -result;
// Print the result
cout << result << " ";
}
}
// Driver code
int main()
{
// Given Input
int n = 5;
int arr[] = { 5, -3, -2, 9, 4 };
// Function Call
minSubarraySum(arr, n);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Kadane's Algorithm to find max
// sum subarray
static int kadane(int arr[], int start, int end)
{
int currMax = arr[start];
int maxSoFar = arr[start];
// Iterating from start to end
for(int i = start + 1; i < end + 1; i++)
{
currMax = Math.max(arr[i], arr[i] + currMax);
maxSoFar = Math.max(maxSoFar, currMax);
}
// Returning maximum sum
return maxSoFar;
}
// Function to find the minimum subarray
// sum for each suffix
static void minSubarraySum(int arr[], int n)
{
// Inverting all the elements of
// array arr[].
for(int i = 0; i < n; i++)
{
arr[i] = -arr[i];
}
// Finding the result for each
// subarray
for(int i = 0; i < n; i++)
{
// Finding the max subarray sum
int result = kadane(arr, i, n - 1);
// Inverting the result
result = -result;
// Print the result
System.out.print(result + " ");
}
}
// Driver code
public static void main(String[] args)
{
// Given Input
int n = 5;
int arr[] = { 5, -3, -2, 9, 4 };
// Function Call
minSubarraySum(arr, n);
}
}
// This code is contributed by Potta Lokesh
Python3
# Python3 program for the above approach # Kadane's Algorithm to find max # sum subarray def kadane(arr, start, end): currMax = arr[start] maxSoFar = arr[start] # Iterating from start to end for i in range(start + 1,end + 1, 1): currMax = max(arr[i], arr[i] + currMax) maxSoFar = max(maxSoFar, currMax) # Returning maximum sum return maxSoFar # Function to find the minimum subarray # sum for each suffix def minSubarraySum(arr, n): # Inverting all the elements of # array arr[]. for i in range(n): arr[i] = -arr[i] # Finding the result for each # subarray for i in range(n): # Finding the max subarray sum result = kadane(arr, i, n - 1) # Inverting the result result = -result # Print the result print(result, end = " ") # Driver code if __name__ == '__main__': # Given Input n = 5 arr = [ 5, -3, -2, 9, 4 ] # Function Call minSubarraySum(arr, n) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG{
// Kadane's Algorithm to find max
// sum subarray
static int kadane(int []arr, int start, int end)
{
int currMax = arr[start];
int maxSoFar = arr[start];
// Iterating from start to end
for(int i = start + 1; i < end + 1; i++)
{
currMax = Math.Max(arr[i], arr[i] + currMax);
maxSoFar = Math.Max(maxSoFar, currMax);
}
// Returning maximum sum
return maxSoFar;
}
// Function to find the minimum subarray
// sum for each suffix
static void minSubarraySum(int []arr, int n)
{
// Inverting all the elements of
// array arr[].
for(int i = 0; i < n; i++)
{
arr[i] = -arr[i];
}
// Finding the result for each
// subarray
for(int i = 0; i < n; i++)
{
// Finding the max subarray sum
int result = kadane(arr, i, n - 1);
// Inverting the result
result = -result;
// Print the result
Console.Write(result + " ");
}
}
// Driver code
public static void Main(String[] args)
{
// Given Input
int n = 5;
int []arr = { 5, -3, -2, 9, 4 };
// Function Call
minSubarraySum(arr, n);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program for the above approach
// Kadane's Algorithm to find max
// sum subarray
function kadane(arr, start, end)
{
let currMax = arr[start];
let maxSoFar = arr[start];
// Iterating from start to end
for(let i = start + 1; i < end + 1; i++)
{
currMax = Math.max(arr[i], arr[i] + currMax);
maxSoFar = Math.max(maxSoFar, currMax);
}
// Returning maximum sum
return maxSoFar;
}
// Function to find the minimum subarray
// sum for each suffix
function minSubarraySum(arr, n)
{
// Inverting all the elements of
// array arr[].
for(let i = 0; i < n; i++)
{
arr[i] = -arr[i];
}
// Finding the result for each
// subarray
for(let i = 0; i < n; i++)
{
// Finding the max subarray sum
let result = kadane(arr, i, n - 1);
// Inverting the result
result = -result;
// Print the result
document.write(result + " ");
}
}
// Driver code
// Given Input
let n = 5;
let arr = [ 5, -3, -2, 9, 4 ];
// Function Call
minSubarraySum(arr, n);
// This code is contributed by gfgking
</script>
Producción
-5 -5 -2 4 4
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array