Count of ways to split an Array into three contiguous Subarrays having increasing Sum | Function to count the number of ways to split array into three contiguous subarrays of the required type ; Stores the prefix sums ; Stores the suffix sums ; Traverse the given array ; Updating curr_subarray_sum until it is less than prefix_sum [ s - 1 ] ; Increase count ; Decrease curr_subarray_sum by arr [ s [ ] ; Return count ; Driver code
def findCount ( arr , n ) : NEW_LINE INDENT prefix_sum = [ 0 for x in range ( 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 for x in range ( 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 s = 1 NEW_LINE e = 1 NEW_LINE curr_subarray_sum = 0 NEW_LINE count = 0 NEW_LINE while ( s < n - 1 and e < n - 1 ) : NEW_LINE INDENT while ( e < n - 1 and curr_subarray_sum < prefix_sum [ s - 1 ] ) : NEW_LINE INDENT curr_subarray_sum += arr [ e ] NEW_LINE e += 1 NEW_LINE DEDENT if ( curr_subarray_sum <= suffix_sum [ e ] ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT curr_subarray_sum -= arr [ s ] NEW_LINE s += 1 NEW_LINE DEDENT return count NEW_LINE DEDENT arr = [ 2 , 3 , 1 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findCount ( arr , n ) ) NEW_LINE