Maximum sum of pairwise product in an array with negative allowed | PHP program for above implementation ; Function to find the maximum sum ; Sort the array first ; First multiply negative numbers pairwise and sum up from starting as to get maximum sum . ; Second multiply positive numbers pairwise and summed up from the last as to get maximum sum . ; To handle case if positive and negative numbers both are odd in counts . ; If one of them occurs odd times ; Driver code
< ? php $ Mod = 1000000007 ; function findSum ( & $ arr , $ n ) { global $ Mod ; $ sum = 0 ; sort ( $ arr ) ; $ i = 0 ; while ( $ i < $ n && $ arr [ $ i ] < 0 ) { if ( $ i != $ n - 1 && $ arr [ $ i + 1 ] <= 0 ) { $ sum = ( $ sum + ( $ arr [ $ i ] * $ arr [ $ i + 1 ] ) % $ Mod ) % $ Mod ; $ i += 2 ; } else break ; } $ j = $ n - 1 ; while ( $ j >= 0 && $ arr [ $ j ] > 0 ) { if ( $ j != 0 && $ arr [ $ j - 1 ] > 0 ) { $ sum = ( $ sum + ( $ arr [ $ j ] * $ arr [ $ j - 1 ] ) % $ Mod ) % $ Mod ; $ j -= 2 ; } else break ; } if ( $ j > $ i ) $ sum = ( $ sum + ( $ arr [ $ i ] * $ arr [ $ j ] ) % $ Mod ) % $ Mod ; else if ( $ i == $ j ) $ sum = ( $ sum + $ arr [ $ i ] ) % Mod ; return $ sum ; } $ arr = array ( -1 , 9 , 4 , 5 , -4 , 7 ) ; $ n = sizeof ( $ arr ) ; echo findSum ( $ arr , $ n ) ; ? >