Given an array containing N integers. The task is to find the sum of the elements of the contiguous subarray having the smallest(minimum) sum.
Examples:
Input: arr[] = {3, -4, 2, -3, -1, 7, -5}
Output:-6
Input: arr = {2, 6, 8, 1, 4}
Output: 1
An approach has already been discussed in the previous post. In this post, a solution using the approach of Largest Sum Contiguous Subarray is discussed. This is based on the fact that in order to find the minimum contiguous sum we can first make the elements of the original array negative ie. Replace each ar[i] by -ar[i] and then apply Kadane Algorithm. Clearly, if this is the max sum formed then the minimum sum would be the negative of this sum.
Below is the implementation of above approach:
C++
// C++ program for// Smallest sum contiguous subarray | Set 2#include <bits/stdc++.h>using namespace std;// function to find the smallest sum contiguous subarrayint 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 Codeint 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 2import java.io.*;class GFG {// function to find the // smallest sum contiguous// subarraystatic 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 Codepublic 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 subarraydef 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 Codearr = [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 2using System;class GFG {// function to find the // smallest sum contiguous// subarraystatic 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 Codepublic 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// subarrayfunction 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> |
Output:
Smallest sum: -6
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
