Pyramid form ( increasing then decreasing ) consecutive array using reduce operations | Returns minimum cost to form a pyramid ; Store the maximum possible pyramid height ; Maximum height at start is 1 ; For each position calculate maximum height ; Maximum height at end is 1 ; For each position calculate maximum height ; Find minimum possible among calculated values ; Find maximum height of pyramid ; Calculate cost of this pyramid ; Calculate cost of left half ; Calculate cost of right half ; Driver Code
def minPyramidCost ( arr : list , N ) : NEW_LINE INDENT left = [ 0 ] * N NEW_LINE right = [ 0 ] * N NEW_LINE left [ 0 ] = min ( arr [ 0 ] , 1 ) NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT left [ i ] = min ( arr [ i ] , min ( left [ i - 1 ] + 1 , i + 1 ) ) NEW_LINE DEDENT right [ N - 1 ] = min ( arr [ N - 1 ] , 1 ) NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT right [ i ] = min ( arr [ i ] , min ( right [ i + 1 ] + 1 , N - i ) ) NEW_LINE DEDENT tot = [ 0 ] * N NEW_LINE for i in range ( N ) : NEW_LINE INDENT tot [ i ] = min ( right [ i ] , left [ i ] ) NEW_LINE DEDENT max_ind = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if tot [ i ] > tot [ max_ind ] : NEW_LINE INDENT max_ind = i NEW_LINE DEDENT DEDENT cost = 0 NEW_LINE height = tot [ max_ind ] NEW_LINE for x in range ( max_ind , - 1 , - 1 ) : NEW_LINE INDENT cost += arr [ x ] - height NEW_LINE if height > 0 : NEW_LINE INDENT height -= 1 NEW_LINE DEDENT DEDENT height = tot [ max_ind ] - 1 NEW_LINE for x in range ( max_ind + 1 , N ) : NEW_LINE INDENT cost += arr [ x ] - height NEW_LINE if height > 0 : NEW_LINE INDENT height -= 1 NEW_LINE DEDENT DEDENT return cost NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 2 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE print ( minPyramidCost ( arr , N ) ) NEW_LINE DEDENT