Maximum sum bitonic subarray | Function to find the maximum sum bitonic subarray . ; to store the maximum sum bitonic subarray ; Find the longest increasing subarray starting at i . ; Now we know that a [ i . . j ] is an increasing subarray . Remove non - positive elements from the left side as much as possible . ; Find the longest decreasing subarray starting at j . ; Now we know that a [ j . . k ] is a decreasing subarray . Remove non - positive elements from the right side as much as possible . last is needed to keep the last seen element . ; Compute the max sum of the increasing part . ; Compute the max sum of the decreasing part . ; The overall max sum is the sum of both parts minus the peak element , because it was counted twice . ; If the next element is equal to the current , i . e . arr [ i + 1 ] == arr [ i ] , last == i . To ensure the algorithm has progress , get the max of last and i + 1. ; required maximum sum ; The example from the article , the answer is 19. ; Always increasing , the answer is 15. ; Always decreasing , the answer is 15. ; All are equal , the answer is 5. ; The whole array is bitonic , but the answer is 7. ; The answer is 4 ( the tail ) .
def maxSumBitonicSubArr ( arr , n ) : NEW_LINE INDENT max_sum = - 10 ** 9 NEW_LINE i = 0 NEW_LINE while ( i < n ) : NEW_LINE INDENT j = i NEW_LINE while ( j + 1 < n and arr [ j ] < arr [ j + 1 ] ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT while ( i < j and arr [ i ] <= 0 ) : NEW_LINE INDENT i += 1 NEW_LINE DEDENT k = j NEW_LINE while ( k + 1 < n and arr [ k ] > arr [ k + 1 ] ) : NEW_LINE INDENT k += 1 NEW_LINE DEDENT last = k NEW_LINE while ( k > j and arr [ k ] <= 0 ) : NEW_LINE INDENT k -= 1 NEW_LINE DEDENT nn = arr [ i : j + 1 ] NEW_LINE sum_inc = sum ( nn ) NEW_LINE nn = arr [ j : k + 1 ] NEW_LINE sum_dec = sum ( nn ) NEW_LINE sum_all = sum_inc + sum_dec - arr [ j ] NEW_LINE max_sum = max ( [ max_sum , sum_inc , sum_dec , sum_all ] ) NEW_LINE i = max ( last , i + 1 ) NEW_LINE 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 ▁ = ▁ " , maxSumBitonicSubArr ( arr , n ) ) NEW_LINE arr2 = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE n2 = len ( arr2 ) NEW_LINE print ( " Maximum ▁ Sum ▁ = ▁ " , maxSumBitonicSubArr ( arr2 , n2 ) ) NEW_LINE arr3 = [ 5 , 4 , 3 , 2 , 1 ] NEW_LINE n3 = len ( arr3 ) NEW_LINE print ( " Maximum ▁ Sum ▁ = ▁ " , maxSumBitonicSubArr ( arr3 , n3 ) ) NEW_LINE arr4 = [ 5 , 5 , 5 , 5 ] NEW_LINE n4 = len ( arr4 ) NEW_LINE print ( " Maximum ▁ Sum ▁ = ▁ " , maxSumBitonicSubArr ( arr4 , n4 ) ) NEW_LINE arr5 = [ - 1 , 0 , 1 , 2 , 3 , 1 , 0 , - 1 , - 10 ] NEW_LINE n5 = len ( arr5 ) NEW_LINE print ( " Maximum ▁ Sum ▁ = ▁ " , maxSumBitonicSubArr ( arr5 , n5 ) ) NEW_LINE arr6 = [ - 1 , 0 , 1 , 2 , 0 , - 1 , - 2 , 0 , 1 , 3 ] NEW_LINE n6 = len ( arr6 ) NEW_LINE print ( " Maximum ▁ Sum ▁ = ▁ " , maxSumBitonicSubArr ( arr6 , n6 ) ) NEW_LINE