Maximize product of subarray sum with its maximum element | C ++ program for the above approach ; Function to find the maximum product of the sum of the subarray with its maximum element ; Traverse the array arr [ ] ; Increment currSum by a [ i ] ; Maximize the value of currMax ; Maximize the value of largestSum ; If currSum goes less than 0 then update currSum = 0 ; Return the resultant value ; Function to maximize the product of the sum of the subarray with its maximum element ; Find the largest sum of the subarray ; Multiply each array element with - 1 ; Find the largest sum of the subarray with negation of all array element ; Return the resultant maximum value ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int Kadane ( int arr [ ] , int n ) { int largestSum = 0 , currMax = 0 ; int currSum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { currSum += arr [ i ] ; currMax = max ( currMax , arr [ i ] ) ; largestSum = max ( largestSum , currMax * currSum ) ; if ( currSum < 0 ) { currMax = 0 ; currSum = 0 ; } } return largestSum ; } int maximumWeight ( int arr [ ] , int n ) { int largestSum = Kadane ( arr , n ) ; for ( int i = 0 ; i < n ; i ++ ) { arr [ i ] = - arr [ i ] ; } largestSum = max ( largestSum , Kadane ( arr , n ) ) ; return largestSum ; } int main ( ) { int arr [ ] = { 2 , -3 , 8 , -2 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maximumWeight ( arr , N ) ; return 0 ; }