Minimize sum by dividing all elements of a subarray by K | C ++ implementation of the approach ; Function to return the maximum subarray sum ; Function to return the minimized sum of the array elements after performing the given operation ; Find maximum subarray sum ; Find total sum of the array ; Maximum subarray sum is already negative ; Choose the subarray whose sum is maximum and divide all elements by K ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSubArraySum ( int a [ ] , int size ) { int max_so_far = INT_MIN , max_ending_here = 0 ; for ( int i = 0 ; i < size ; i ++ ) { max_ending_here = max_ending_here + a [ i ] ; if ( max_so_far < max_ending_here ) max_so_far = max_ending_here ; if ( max_ending_here < 0 ) max_ending_here = 0 ; } return max_so_far ; } double minimizedSum ( int a [ ] , int n , int K ) { int sum = maxSubArraySum ( a , n ) ; double totalSum = 0 ; for ( int i = 0 ; i < n ; i ++ ) totalSum += a [ i ] ; if ( sum < 0 ) return totalSum ; totalSum = totalSum - sum + ( double ) sum / ( double ) K ; return totalSum ; } int main ( ) { int a [ ] = { 1 , -2 , 3 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int K = 2 ; cout << minimizedSum ( a , n , K ) ; return 0 ; }