Maximum sum bitonic subarray | C ++ implementation to find the 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 ; Driver program to test above ; 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 ) .
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSumBitonicSubArr ( int arr [ ] , int n ) { int max_sum = INT_MIN ; int i = 0 ; while ( i < n ) { int j = i ; while ( j + 1 < n && arr [ j ] < arr [ j + 1 ] ) j ++ ; while ( i < j && arr [ i ] <= 0 ) i ++ ; int k = j ; while ( k + 1 < n && arr [ k ] > arr [ k + 1 ] ) k ++ ; int last = k ; while ( k > j && arr [ k ] <= 0 ) k -- ; int sum_inc = accumulate ( arr + i , arr + j + 1 , 0 ) ; int sum_dec = accumulate ( arr + j , arr + k + 1 , 0 ) ; int sum_all = sum_inc + sum_dec - arr [ j ] ; max_sum = max ( { max_sum , sum_inc , sum_dec , sum_all } ) ; i = max ( last , i + 1 ) ; } return max_sum ; } int main ( ) { int arr [ ] = { 5 , 3 , 9 , 2 , 7 , 6 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Maximum ▁ Sum ▁ = ▁ " << maxSumBitonicSubArr ( arr , n ) << endl ; int arr2 [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n2 = sizeof ( arr2 ) / sizeof ( arr2 [ 0 ] ) ; cout << " Maximum ▁ Sum ▁ = ▁ " << maxSumBitonicSubArr ( arr2 , n2 ) << endl ; int arr3 [ ] = { 5 , 4 , 3 , 2 , 1 } ; int n3 = sizeof ( arr3 ) / sizeof ( arr3 [ 0 ] ) ; cout << " Maximum ▁ Sum ▁ = ▁ " << maxSumBitonicSubArr ( arr3 , n3 ) << endl ; int arr4 [ ] = { 5 , 5 , 5 , 5 } ; int n4 = sizeof ( arr4 ) / sizeof ( arr4 [ 0 ] ) ; cout << " Maximum ▁ Sum ▁ = ▁ " << maxSumBitonicSubArr ( arr4 , n4 ) << endl ; int arr5 [ ] = { -1 , 0 , 1 , 2 , 3 , 1 , 0 , -1 , -10 } ; int n5 = sizeof ( arr5 ) / sizeof ( arr5 [ 0 ] ) ; cout << " Maximum ▁ Sum ▁ = ▁ " << maxSumBitonicSubArr ( arr5 , n5 ) << endl ; int arr6 [ ] = { -1 , 0 , 1 , 2 , 0 , -1 , -2 , 0 , 1 , 3 } ; int n6 = sizeof ( arr6 ) / sizeof ( arr6 [ 0 ] ) ; cout << " Maximum ▁ Sum ▁ = ▁ " << maxSumBitonicSubArr ( arr6 , n6 ) << endl ; return 0 ; }