Subarray with largest sum after excluding its maximum element | C ++ implementation to find the maximum sum subarray such by excluding the maximum element from the subarray ; Function to find the maximum sum subarray by excluding the maximum element from the array ; Loop to store all the positive elements in the map ; Loop to iterating over the map and considering as the maximum element of the current including subarray ; Make the current element maximum ; Iterate through array and apply kadane 's algorithm ; Condition if current element is greater than mx then make the element - infinity ; Store the indices in some variable ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void maximumSumSubarray ( int arr [ ] , int n ) { unordered_map < int , int > mp ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] >= 0 && mp . find ( arr [ i ] ) == mp . end ( ) ) mp [ arr [ i ] ] = 1 ; } int first = 0 ; int last = 0 ; int ans = 0 ; int INF = 1e6 ; for ( auto i : mp ) { int mx = i . first ; int curr = 0 ; int curr_start ; for ( int j = 0 ; j < n ; j ++ ) { if ( curr == 0 ) curr_start = j ; int val = arr [ j ] > mx ? - INF : arr [ j ] ; curr += val ; if ( curr < 0 ) curr = 0 ; if ( curr > ans ) { ans = curr ; first = curr_start ; last = j ; } } } cout << first + 1 << " ▁ " << last + 1 ; } int main ( ) { int arr [ ] = { 5 , -2 , 10 , -1 , 4 } ; int size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; maximumSumSubarray ( arr , size ) ; return 0 ; }