Subarray with largest sum after excluding its maximum element | Java 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
import java . util . * ; class GFG { static void maximumSumSubarray ( int arr [ ] , int n ) { Map < Integer , Integer > mp = new HashMap < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] >= 0 ) mp . put ( arr [ i ] , 1 ) ; } int first = 0 ; int last = 0 ; int ans = 0 ; int INF = ( int ) 1e6 ; for ( Map . Entry < Integer , Integer > i : mp . entrySet ( ) ) { int mx = i . getKey ( ) ; int curr = 0 ; int curr_start = - 1 ; 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 ; } } } System . out . print ( ( first + 1 ) + " ▁ " + ( last + 1 ) ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 5 , - 2 , 10 , - 1 , 4 } ; int size = arr . length ; maximumSumSubarray ( arr , size ) ; } }