Maximum sum bitonic subarray | function to find the maximum sum bitonic subarray ; ' msis [ ] ' to store the maximum sum increasing subarray up to each index of ' arr ' from the beginning ' msds [ ] ' to store the maximum sum decreasing subarray from each index of ' arr ' up to the end ; to store the maximum sum bitonic subarray ; building up the maximum sum increasing subarray for each array index ; building up the maximum sum decreasing subarray for each array index ; for each array index , calculating the maximum sum of bitonic subarray of which it is a part of ; if true , then update ' max ' bitonic subarray sum ; required maximum sum ; Driver Code
def maxSumBitonicSubArr ( arr , n ) : NEW_LINE INDENT msis = [ None ] * n NEW_LINE msds = [ None ] * n NEW_LINE max_sum = 0 NEW_LINE msis [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( arr [ i ] > arr [ i - 1 ] ) : NEW_LINE INDENT msis [ i ] = msis [ i - 1 ] + arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT msis [ i ] = arr [ i ] NEW_LINE DEDENT DEDENT msds [ n - 1 ] = arr [ n - 1 ] NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( arr [ i ] > arr [ i + 1 ] ) : NEW_LINE INDENT msds [ i ] = msds [ i + 1 ] + arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT msds [ i ] = arr [ i ] NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ( max_sum < ( msis [ i ] + msds [ i ] - arr [ i ] ) ) : NEW_LINE INDENT max_sum = ( msis [ i ] + msds [ i ] - arr [ i ] ) NEW_LINE DEDENT DEDENT return max_sum NEW_LINE DEDENT arr = [ 5 , 3 , 9 , 2 , 7 , 6 , 4 ] ; NEW_LINE n = len ( arr ) NEW_LINE print ( " Maximum ▁ Sum ▁ = ▁ " + str ( maxSumBitonicSubArr ( arr , n ) ) ) NEW_LINE