Maximum subarray sum with same first and last element formed by removing elements | C ++ program for the above approach ; Function to find the maximum sum of sub - array ; Initialize the variables ; Traverse over the range ; Add the current value to the variable currsum for prefix sum ; Calculate the result ; Return the answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumSubarraySum ( vector < int > & arr ) { int N = arr . size ( ) ; unordered_map < int , int > memo ; int res = INT_MIN ; int currsum = 0 , currval = 0 ; for ( int i = 0 ; i < N ; ++ i ) { currval = arr [ i ] ; currsum = currsum + currval ; if ( memo . count ( currval ) != 0 ) { if ( currval > 0 ) res = max ( res , currsum - memo [ currval ] + currval ) ; else res = max ( res , currsum - memo [ currval ] + 2 * currval ) ; } else memo [ currval ] = currsum ; if ( currval < 0 ) currsum = currsum - currval ; } return res ; } int main ( ) { vector < int > arr = { -1 , -3 , 4 , 0 , -1 , -2 } ; cout << maximumSubarraySum ( arr ) ; return 0 ; }