Maximum Subarray Sum Excluding Certain Elements | C ++ Program to find max subarray sum excluding some elements ; Function to check the element present in array B ; Utility function for findMaxSubarraySum ( ) with the following parameters A = > Array A , B = > Array B , n = > Number of elements in Array A , m = > Number of elements in Array B ; set max_so_far to INT_MIN ; if the element is present in B , set current max to 0 and move to the next element ; Proceed as in Kadane 's Algorithm ; Wrapper for findMaxSubarraySumUtil ( ) ; This case will occour when all elements of A are present in B , thus no subarray can be formed ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPresent ( int B [ ] , int m , int x ) { for ( int i = 0 ; i < m ; i ++ ) if ( B [ i ] == x ) return true ; return false ; } int findMaxSubarraySumUtil ( int A [ ] , int B [ ] , int n , int m ) { int max_so_far = INT_MIN , curr_max = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( isPresent ( B , m , A [ i ] ) ) { curr_max = 0 ; continue ; } curr_max = max ( A [ i ] , curr_max + A [ i ] ) ; max_so_far = max ( max_so_far , curr_max ) ; } return max_so_far ; } void findMaxSubarraySum ( int A [ ] , int B [ ] , int n , int m ) { int maxSubarraySum = findMaxSubarraySumUtil ( A , B , n , m ) ; if ( maxSubarraySum == INT_MIN ) { cout << " Maximum ▁ Subarray ▁ Sum ▁ cant ▁ be ▁ found " << endl ; } else { cout << " The ▁ Maximum ▁ Subarray ▁ Sum ▁ = ▁ " << maxSubarraySum << endl ; } } int main ( ) { int A [ ] = { 3 , 4 , 5 , -4 , 6 } ; int B [ ] = { 1 , 8 , 5 } ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int m = sizeof ( B ) / sizeof ( B [ 0 ] ) ; findMaxSubarraySum ( A , B , n , m ) ; return 0 ; }