Maximize subarrays count containing the maximum and minimum Array element after deleting at most one element | C ++ program for the above approach ; Returns the count of subarrays which contains both the maximum and minimum elements in the given vector ; Initialize the low and high of array ; If current element is less than least element ; If current element is more than highest element ; If current element is equal to low or high then update the pointers ; Update number of subarrays ; Return the result ; Function to find the maximum count of subarrays ; Iterate the array to find the maximum and minimum element ; Vector after removing the minimum element ; Using assignment operator to copy one vector to other ; Vector after removing the maximum element ; Driver Code ; Given array ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long proc ( vector < int > & v ) { long long int n = v . size ( ) ; int low = v [ n - 1 ] , high = v [ n - 1 ] ; long long int p1 = n , p2 = n ; long long ans = 0 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { int x = v [ i ] ; if ( x < low ) { low = x ; ans = 0 ; } else if ( x > high ) { high = x ; ans = 0 ; } if ( x == low ) p1 = i ; if ( x == high ) p2 = i ; ans += n - max ( p1 , p2 ) ; } return ans ; } long long subarray ( vector < int > & v ) { long long int n = v . size ( ) ; if ( n <= 1 ) return n ; long long ans = proc ( v ) ; int low = v [ 0 ] , pos_low = 0 , high = v [ 0 ] , pos_high = 0 ; for ( int i = 1 ; i < n ; i ++ ) { int x = v [ i ] ; if ( x < low ) { low = x ; pos_low = i ; } else if ( x > high ) { high = x ; pos_high = i ; } } vector < int > u ; u = v ; u . erase ( u . begin ( ) + pos_low ) ; ans = max ( ans , proc ( u ) ) ; vector < int > w ; w = v ; w . erase ( w . begin ( ) + pos_high ) ; return max ( ans , proc ( w ) ) ; } int main ( ) { vector < int > v ; v . push_back ( 7 ) ; v . push_back ( 2 ) ; v . push_back ( 5 ) ; v . push_back ( 4 ) ; v . push_back ( 3 ) ; v . push_back ( 1 ) ; cout << subarray ( v ) << endl ; return 0 ; }