Minimize the sum of pair which upon removing divides the Array into 3 subarrays | Python 3 implementation of the above approach ; Function to find minimum possible sum of pair which breaks the array into 3 non - empty subarrays ; prefixMin [ i ] contains minimum element till i ; Driver Code ; Given array
import sys NEW_LINE def minSumPair ( arr , N ) : NEW_LINE INDENT if ( N < 5 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT prefixMin = [ 0 for i in range ( N ) ] NEW_LINE prefixMin [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , N - 1 , 1 ) : NEW_LINE INDENT prefixMin [ i ] = min ( arr [ i ] , prefixMin [ i - 1 ] ) NEW_LINE DEDENT ans = sys . maxsize NEW_LINE for i in range ( 3 , N - 1 , 1 ) : NEW_LINE INDENT ans = min ( ans , arr [ i ] + prefixMin [ i - 2 ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 5 , 2 , 4 , 6 , 3 , 7 ] NEW_LINE N = len ( arr ) NEW_LINE print ( minSumPair ( arr , N ) ) NEW_LINE DEDENT