Maximum sum subarray removing at most one element | Java program to get maximum sum subarray removing at - most one element ; Method returns maximum sum of all subarray where removing one element is also allowed ; Maximum sum subarrays in forward and backward directions ; Initialize current max and max so far . ; calculating maximum sum subarrays in forward direction ; storing current maximum till ith , in forward array ; calculating maximum sum subarrays in backward direction ; storing current maximum from ith , in backward array ; Initializing final ans by max_so_far so that , case when no element is removed to get max sum subarray is also handled ; choosing maximum ignoring ith element ; Driver code
class GFG { static int maxSumSubarrayRemovingOneEle ( int arr [ ] , int n ) { int fw [ ] = new int [ n ] ; int bw [ ] = new int [ n ] ; int cur_max = arr [ 0 ] , max_so_far = arr [ 0 ] ; fw [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { cur_max = Math . max ( arr [ i ] , cur_max + arr [ i ] ) ; max_so_far = Math . max ( max_so_far , cur_max ) ; fw [ i ] = cur_max ; } cur_max = max_so_far = bw [ n - 1 ] = arr [ n - 1 ] ; for ( int i = n - 2 ; i >= 0 ; i -- ) { cur_max = Math . max ( arr [ i ] , cur_max + arr [ i ] ) ; max_so_far = Math . max ( max_so_far , cur_max ) ; bw [ i ] = cur_max ; } int fans = max_so_far ; for ( int i = 1 ; i < n - 1 ; i ++ ) fans = Math . max ( fans , fw [ i - 1 ] + bw [ i + 1 ] ) ; return fans ; } public static void main ( String arg [ ] ) { int arr [ ] = { - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 } ; int n = arr . length ; System . out . print ( maxSumSubarrayRemovingOneEle ( arr , n ) ) ; } }