Maximize product of subarray sum with its maximum element | 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
def Kadane ( arr , n ) : NEW_LINE INDENT largestSum = 0 NEW_LINE currMax = 0 NEW_LINE currSum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT currSum += arr [ i ] NEW_LINE currMax = max ( currMax , arr [ i ] ) NEW_LINE largestSum = max ( largestSum , currMax * currSum ) NEW_LINE if ( currSum < 0 ) : NEW_LINE INDENT currMax = 0 NEW_LINE currSum = 0 NEW_LINE DEDENT DEDENT return largestSum NEW_LINE DEDENT def maximumWeight ( arr , n ) : NEW_LINE INDENT largestSum = Kadane ( arr , n ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT arr [ i ] = - arr [ i ] NEW_LINE DEDENT largestSum = max ( largestSum , Kadane ( arr , n ) ) NEW_LINE return largestSum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , - 3 , 8 , - 2 , 5 ] NEW_LINE N = len ( arr ) NEW_LINE print ( maximumWeight ( arr , N ) ) NEW_LINE DEDENT