Split the given array into K sub | Function to check if mid can be maximum sub - arrays sum ; If individual element is greater maximum possible sum ; Increase sum of current sub - array ; If the sum is greater than mid increase count ; Check condition ; Function to find maximum subarray sum which is minimum ; start = max ( array ) Max subarray sum , considering subarray of length 1 ; Answer stores possible maximum sub array sum ; If mid is possible solution Put answer = mid ; ; Driver Code
def check ( mid , array , n , K ) : NEW_LINE INDENT count = 0 NEW_LINE sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( array [ i ] > mid ) : NEW_LINE INDENT return False NEW_LINE DEDENT sum += array [ i ] NEW_LINE if ( sum > mid ) : NEW_LINE INDENT count += 1 NEW_LINE sum = array [ i ] NEW_LINE DEDENT DEDENT count += 1 NEW_LINE if ( count <= K ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def solve ( array , n , K ) : NEW_LINE INDENT end = 0 NEW_LINE for i in range ( n ) : NEW_LINE answer = 0 NEW_LINE while ( start <= end ) : NEW_LINE INDENT mid = ( start + end ) // 2 NEW_LINE if ( check ( mid , array , n , K ) ) : NEW_LINE INDENT answer = mid NEW_LINE end = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT start = mid + 1 NEW_LINE DEDENT DEDENT return answer NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT array = [ 1 , 2 , 3 , 4 ] NEW_LINE n = len ( array ) NEW_LINE K = 3 NEW_LINE print ( solve ( array , n , K ) ) NEW_LINE DEDENT