Dada una array que contiene N enteros. La tarea es encontrar la suma de los elementos del subarreglo contiguo que tiene la suma más pequeña (mínima).
Ejemplos :
Input: arr[] = {3, -4, 2, -3, -1, 7, -5}
Output:-6
Input: arr = {2, 6, 8, 1, 4}
Output: 1
Ya se ha discutido un enfoque en la publicación anterior . En esta publicación, se analiza una solución que utiliza el enfoque del subarreglo contiguo de suma más grande . Esto se basa en el hecho de que para encontrar la suma contigua mínima, primero podemos hacer que los elementos de la array original sean negativos, es decir. Reemplace cada ar[i] por -ar[i] y luego aplique el Algoritmo de Kadane . Claramente, si esta es la suma máxima formada, la suma mínima sería el negativo de esta suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for
// Smallest sum contiguous subarray | Set 2
#include <bits/stdc++.h>
using namespace std;
// function to find the smallest sum contiguous subarray
int smallestSumSubarr(int arr[], int n)
{
// First invert the sign of the elements
for (int i = 0; i < n; i++)
arr[i] = -arr[i];
// Apply the normal Kadane algorithm But on the elements
// Of the array having inverted sign
int sum_here = arr[0], max_sum = arr[0];
for (int i = 1; i < n; i++) {
sum_here = max(sum_here + arr[i], arr[i]);
max_sum = max(max_sum, sum_here);
}
// Invert the answer to get minimum val
return (-1) * max_sum;
}
// Driver Code
int main()
{
int arr[] = { 3, -4, 2, -3, -1, 7, -5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Smallest sum: "
<< smallestSumSubarr(arr, n);
return 0;
}
Java
// Java program for Smallest
// sum contiguous subarray | Set 2
import java.io.*;
class GFG
{
// function to find the
// smallest sum contiguous
// subarray
static int smallestSumSubarr(int arr[],
int n)
{
// First invert the
// sign of the elements
for (int i = 0; i < n; i++)
arr[i] = -arr[i];
// Apply the normal Kadane
// algorithm But on the
// elements Of the array
// having inverted sign
int sum_here = arr[0],
max_sum = arr[0];
for (int i = 1; i < n; i++)
{
sum_here = Math.max(sum_here +
arr[i], arr[i]);
max_sum = Math.max(max_sum,
sum_here);
}
// Invert the answer
// to get minimum val
return (-1) * max_sum;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {3, -4, 2, -3,
-1, 7, -5};
int n = arr.length;
System.out.print("Smallest sum: " +
smallestSumSubarr(arr, n));
}
}
// This code is contributed
// by inder_verma.
Python3
# Python3 program for
# Smallest sum contiguous subarray | Set 2
# function to find the smallest
# sum contiguous subarray
def smallestSumSubarr(arr, n):
# First invert the sign of the elements
for i in range(n):
arr[i] = -arr[i]
# Apply the normal Kadane algorithm but
# on the elements of the array having inverted sign
sum_here = arr[0]
max_sum = arr[0]
for i in range(1, n):
sum_here = max(sum_here + arr[i], arr[i])
max_sum = max(max_sum, sum_here)
# Invert the answer to get minimum val
return (-1) * max_sum
# Driver Code
arr = [3, -4, 2, -3, -1, 7, -5]
n = len(arr)
print("Smallest sum:",
smallestSumSubarr(arr, n))
# This code is contributed by Mohit Kumar
C#
// C# program for Smallest
// sum contiguous subarray | Set 2
using System;
class GFG
{
// function to find the
// smallest sum contiguous
// subarray
static int smallestSumSubarr(int []arr,
int n)
{
// First invert the
// sign of the elements
for (int i = 0; i < n; i++)
arr[i] = -arr[i];
// Apply the normal Kadane
// algorithm But on the
// elements Of the array
// having inverted sign
int sum_here = arr[0],
max_sum = arr[0];
for (int i = 1; i < n; i++)
{
sum_here = Math.Max(sum_here +
arr[i], arr[i]);
max_sum = Math.Max(max_sum,
sum_here);
}
// Invert the answer
// to get minimum val
return (-1) * max_sum;
}
// Driver Code
public static void Main ()
{
int []arr = {3, -4, 2, -3,
-1, 7, -5};
int n = arr.Length;
Console.WriteLine("Smallest sum: " +
smallestSumSubarr(arr, n));
}
}
// This code is contributed
// by inder_verma.
PHP
<?php
// PHP program for Smallest sum
// contiguous subarray | Set 2
// Function to find the smallest
// sum contiguous subarray
function smallestSumSubarr($arr, $n)
{
// First invert the sign
// of the elements
for ( $i = 0; $i < $n; $i++)
$arr[$i] = -$arr[$i];
// Apply the normal Kadane algorithm
// but on the elements of the array
// having inverted sign
$sum_here = $arr[0];
$max_sum = $arr[0];
for ($i = 1; $i < $n; $i++)
{
$sum_here = max($sum_here +
$arr[$i], $arr[$i]);
$max_sum = max($max_sum, $sum_here);
}
// Invert the answer to
// get minimum val
return (-1) * $max_sum;
}
// Driver Code
$arr = array( 3, -4, 2, -3, -1, 7, -5 );
$n = sizeof($arr);
echo "Smallest sum: ",
smallestSumSubarr($arr, $n);
// This code is contributed
// by Sach_Code
?>
Javascript
<script>
// JavaScript program for Smallest
// sum contiguous subarray | Set 2
// function to find the
// smallest sum contiguous
// subarray
function smallestSumSubarr(arr, n)
{
// First invert the
// sign of the elements
for (let i = 0; i < n; i++)
arr[i] = -arr[i];
// Apply the normal Kadane
// algorithm But on the
// elements Of the array
// having inverted sign
let sum_here = arr[0],
max_sum = arr[0];
for (let i = 1; i < n; i++)
{
sum_here = Math.max(sum_here +
arr[i], arr[i]);
max_sum = Math.max(max_sum,
sum_here);
}
// Invert the answer
// to get minimum val
return (-1) * max_sum;
}
// driver code
let arr = [3, -4, 2, -3,
-1, 7, -5];
let n = arr.length;
document.write("Smallest sum: " +
smallestSumSubarr(arr, n));
</script>
Producción:
Smallest sum: -6
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por Sagar Pant 1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA