Generate an array of maximum sum such that each element exceeds all elements present either on its left or right | Function to construct the array having maximum sum satisfying the given criteria ; Declaration of the array arrA [ ] and ans [ ] ; Stores the maximum sum of the resultant array ; Initialize the array arrA [ ] ; Traversing the array arrA [ ] ; Initialize the array arrB [ ] ; Assign the maximum element to the current element ; Form the first increasing till every index i ; Make the current element as the maximum element ; Forming decreasing from the index i + 1 to the index N ; Initialize the sum ; Find the total sum ; Check if the total sum is at least the sum found then make ans as ansB ; Print the final array formed ; Driver Code
def maximumSumArray ( arr , N ) : NEW_LINE INDENT arrA = [ 0 ] * N NEW_LINE ans = [ 0 ] * N NEW_LINE maxSum = 0 ; NEW_LINE for i in range ( N ) : NEW_LINE INDENT arrA [ i ] = arr [ i ] ; NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT arrB = [ 0 ] * N NEW_LINE maximum = arrA [ i ] ; NEW_LINE arrB [ i ] = maximum ; NEW_LINE temp = 0 NEW_LINE for j in range ( i - 1 , - 1 , - 1 ) : NEW_LINE INDENT arrB [ j ] = min ( maximum , arrA [ j ] ) ; NEW_LINE maximum = arrB [ j ] ; NEW_LINE temp = j NEW_LINE DEDENT maximum = arrA [ i ] ; NEW_LINE for j in range ( i + 1 , N ) : NEW_LINE INDENT arrB [ j ] = min ( maximum , arrA [ j ] ) ; NEW_LINE maximum = arrB [ j ] ; NEW_LINE DEDENT sum = 0 ; NEW_LINE for j in range ( N ) : NEW_LINE INDENT sum += arrB [ j ] ; NEW_LINE DEDENT if ( sum > maxSum ) : NEW_LINE INDENT maxSum = sum ; NEW_LINE ans = arrB ; NEW_LINE DEDENT DEDENT for val in ans : NEW_LINE INDENT print ( val ) ; NEW_LINE DEDENT DEDENT A = [ 10 , 6 , 8 ] ; NEW_LINE N = len ( A ) NEW_LINE maximumSumArray ( A , N ) ; NEW_LINE