Maximum subarray sum possible after removing at most one subarray | Java program for the above approach ; Function to find maximum subarray sum possible after removing at most one subarray ; Calculate the preSum [ ] array ; Update the value of sum ; Update the value of maxSum ; Update the value of preSum [ i ] ; Calculate the postSum [ ] array ; Update the value of sum ; Update the value of maxSum ; Update the value of postSum [ i ] ; Stores the resultant maximum sum of subarray ; Update the value of ans ; Print the resultant sum ; Driver Code
import java . io . * ; import java . util . * ; class GFG { public static void maximumSum ( int arr [ ] , int n ) { long [ ] preSum = new long [ n ] ; long sum = 0 ; long maxSum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum = Math . max ( arr [ i ] , sum + arr [ i ] ) ; maxSum = Math . max ( maxSum , sum ) ; preSum [ i ] = maxSum ; } sum = 0 ; maxSum = 0 ; long [ ] postSum = new long [ n + 1 ] ; for ( int i = n - 1 ; i >= 0 ; i -- ) { sum = Math . max ( arr [ i ] , sum + arr [ i ] ) ; maxSum = Math . max ( maxSum , sum ) ; postSum [ i ] = maxSum ; } long ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { ans = Math . max ( ans , preSum [ i ] + postSum [ i + 1 ] ) ; } System . out . println ( ans ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 7 , 6 , - 1 , - 4 , - 5 , 7 , 1 } ; maximumSum ( arr , arr . length ) ; } }