Maximum Subarray Sum Excluding Certain Elements | C ++ Program implementation of the above idea ; Function to calculate the max sum of contigous subarray of B whose elements are not present in A ; mark all the elements present in B ; initialize max_so_far with INT_MIN ; traverse the array A ; if current max is greater than max so far then update max so far ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMaxSubarraySum ( vector < int > A , vector < int > B ) { unordered_map < int , int > m ; for ( int i = 0 ; i < B . size ( ) ; i ++ ) { m [ B [ i ] ] = 1 ; } int max_so_far = INT_MIN ; int currmax = 0 ; for ( int i = 0 ; i < A . size ( ) ; i ++ ) { if ( currmax < 0 m [ A [ i ] ] == 1 ) { currmax = 0 ; continue ; } currmax = max ( A [ i ] , A [ i ] + currmax ) ; if ( max_so_far < currmax ) { max_so_far = currmax ; } } return max_so_far ; } int main ( ) { vector < int > a = { 3 , 4 , 5 , -4 , 6 } ; vector < int > b = { 1 , 8 , 5 } ; cout << findMaxSubarraySum ( a , b ) ; return 0 ; }