Split array into two subarrays such that difference of their sum is minimum | Python3 program for the above approach ; Function to return minimum difference between two subarray sums ; To store prefix sums ; Generate prefix sum array ; To store suffix sums ; Generate suffix sum array ; Stores the minimum difference ; Traverse the given array ; Calculate the difference ; Update minDiff ; Return minDiff ; Driver Code ; Given array ; Length of the array
import sys NEW_LINE def minDiffSubArray ( arr , n ) : NEW_LINE INDENT prefix_sum = [ 0 ] * n NEW_LINE prefix_sum [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT prefix_sum [ i ] = ( prefix_sum [ i - 1 ] + arr [ i ] ) NEW_LINE DEDENT suffix_sum = [ 0 ] * n NEW_LINE suffix_sum [ n - 1 ] = arr [ n - 1 ] NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT suffix_sum [ i ] = ( suffix_sum [ i + 1 ] + arr [ i ] ) NEW_LINE DEDENT minDiff = sys . maxsize NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT diff = abs ( prefix_sum [ i ] - suffix_sum [ i + 1 ] ) NEW_LINE if ( diff < minDiff ) : NEW_LINE INDENT minDiff = diff NEW_LINE DEDENT DEDENT return minDiff NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 7 , 9 , 5 , 10 ] NEW_LINE n = len ( arr ) NEW_LINE print ( minDiffSubArray ( arr , n ) ) NEW_LINE DEDENT