Smallest sum contiguous subarray | Set | C ++ program for Smallest sum contiguous subarray | Set 2 ; function to find the smallest sum contiguous subarray ; First invert the sign of the elements ; Apply the normal Kadane algorithm But on the elements Of the array having inverted sign ; Invert the answer to get minimum val ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int smallestSumSubarr ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) arr [ i ] = - arr [ i ] ; 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 ) ; } return ( -1 ) * max_sum ; } 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 ; }