Maximum subarray sum possible after removing at most one subarray | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void maximumSum ( int arr [ ] , int n ) { int preSum [ n ] ; int sum = 0 ; int maxSum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum = max ( arr [ i ] , sum + arr [ i ] ) ; maxSum = max ( maxSum , sum ) ; preSum [ i ] = maxSum ; } sum = 0 ; maxSum = 0 ; int postSum [ n + 1 ] ; for ( int i = n - 1 ; i >= 0 ; i -- ) { sum = max ( arr [ i ] , sum + arr [ i ] ) ; maxSum = max ( maxSum , sum ) ; postSum [ i ] = maxSum ; } int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { ans = max ( ans , preSum [ i ] + postSum [ i ] ) ; } cout << ( ans ) ; } int main ( ) { int arr [ ] = { 7 , 6 , -1 , -4 , -5 , 7 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; maximumSum ( arr , n ) ; return 0 ; }