text: Maximize the sum of array after multiplying a prefix and suffix by | C ++ implementation to find the maximum sum of the array by multiplying the prefix and suffix of the array by - 1 ; Kadane 's algorithm to find the maximum subarray sum ; Loop to find the maximum subarray array sum in the given array ; Function to find the maximum sum of the array by multiplying the prefix and suffix by - 1 ; Total intital sum ; Loop to find the maximum sum of the array ; Maximum value ; Driver Code
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_ending_here < 0 ) max_ending_here = 0 ; if ( max_so_far < max_ending_here ) max_so_far = max_ending_here ; } return max_so_far ; } int maxSum ( int a [ ] , int n ) { int S = 0 ; for ( int i = 0 ; i < n ; i ++ ) S += a [ i ] ; int X = maxSubArraySum ( a , n ) ; return 2 * X - S ; } int main ( ) { int a [ ] = { -1 , -2 , -3 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int max_sum = maxSum ( a , n ) ; cout << max_sum ; return 0 ; }