Temple Offerings | Python3 program to find temple offerings required ; To store count of increasing order temples on left and right ( including current temple ) ; Returns count of minimum offerings for n temples of given heights . ; Initialize counts for all temples ; Values corner temples ; Filling left and right values using same values of previous ( or next ; Computing max of left and right for all temples and returing sum ; Driver code
from typing import List NEW_LINE class Temple : NEW_LINE INDENT def __init__ ( self , l : int , r : int ) : NEW_LINE INDENT self . L = l NEW_LINE self . R = r NEW_LINE DEDENT DEDENT def offeringNumber ( n : int , templeHeight : List [ int ] ) -> int : NEW_LINE INDENT chainSize = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT chainSize [ i ] = Temple ( - 1 , - 1 ) NEW_LINE DEDENT chainSize [ 0 ] . L = 1 NEW_LINE chainSize [ - 1 ] . R = 1 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if templeHeight [ i - 1 ] < templeHeight [ i ] : NEW_LINE INDENT chainSize [ i ] . L = chainSize [ i - 1 ] . L + 1 NEW_LINE DEDENT else : NEW_LINE INDENT chainSize [ i ] . L = 1 NEW_LINE DEDENT DEDENT for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT if templeHeight [ i + 1 ] < templeHeight [ i ] : NEW_LINE INDENT chainSize [ i ] . R = chainSize [ i + 1 ] . R + 1 NEW_LINE DEDENT else : NEW_LINE INDENT chainSize [ i ] . R = 1 NEW_LINE DEDENT DEDENT sm = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sm += max ( chainSize [ i ] . L , chainSize [ i ] . R ) NEW_LINE DEDENT return sm NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr1 = [ 1 , 2 , 2 ] NEW_LINE print ( offeringNumber ( 3 , arr1 ) ) NEW_LINE arr2 = [ 1 , 4 , 3 , 6 , 2 , 1 ] NEW_LINE print ( offeringNumber ( 6 , arr2 ) ) NEW_LINE DEDENT