Maximum sum bitonic subarray | Java 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 code ; 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 ) .
import java . util . * ; class GFG { static int find_partial_sum ( int arr [ ] , int start , int end ) { int sum = 0 ; for ( int i = start ; i < end ; i ++ ) sum += arr [ i ] ; return sum ; } static int maxSumBitonicSubArr ( int arr [ ] , int n ) { int max_sum = - 1000000 ; 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 = find_partial_sum ( arr , i , j + 1 ) ; int sum_dec = find_partial_sum ( arr , j , k + 1 ) ; int sum_all = sum_inc + sum_dec - arr [ j ] ; max_sum = Math . max ( Math . max ( max_sum , sum_inc ) , Math . max ( sum_dec , sum_all ) ) ; i = Math . max ( last , i + 1 ) ; } return max_sum ; } public static void main ( String args [ ] ) { int arr [ ] = { 5 , 3 , 9 , 2 , 7 , 6 , 4 } ; int n = arr . length ; System . out . println ( " Maximum ▁ sum ▁ = ▁ " + maxSumBitonicSubArr ( arr , n ) ) ; int arr2 [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n2 = arr2 . length ; System . out . println ( " Maximum ▁ sum ▁ = ▁ " + maxSumBitonicSubArr ( arr2 , n2 ) ) ; int arr3 [ ] = { 5 , 4 , 3 , 2 , 1 } ; int n3 = arr3 . length ; System . out . println ( " Maximum ▁ sum ▁ = ▁ " + maxSumBitonicSubArr ( arr3 , n3 ) ) ; int arr4 [ ] = { 5 , 5 , 5 , 5 } ; int n4 = arr4 . length ; System . out . println ( " Maximum ▁ sum ▁ = ▁ " + maxSumBitonicSubArr ( arr4 , n4 ) ) ; int arr5 [ ] = { - 1 , 0 , 1 , 2 , 3 , 1 , 0 , - 1 , - 10 } ; int n5 = arr5 . length ; System . out . println ( " Maximum ▁ sum ▁ = ▁ " + maxSumBitonicSubArr ( arr5 , n5 ) ) ; int arr6 [ ] = { - 1 , 0 , 1 , 2 , 0 , - 1 , - 2 , 0 , 1 , 3 } ; int n6 = arr6 . length ; System . out . println ( " Maximum ▁ sum ▁ = ▁ " + maxSumBitonicSubArr ( arr6 , n6 ) ) ; } }