Maximum sum subarray after altering the array | Java implementation of the approach ; Function that returns true if all the array element are <= 0 ; If any element is non - negative ; Function to return the vector representing the right to left Kadane array as described in the approach ; Function to return the prefix_sum vector ; Function to return the maximum sum subarray ; Function to get the maximum sum subarray in the modified array ; kadane_r_to_l [ i ] will store the maximum subarray sum for thre subarray arr [ i ... N - 1 ] ; Get the prefix sum array ; To get max_prefix_sum_at_any_index ; Summation of both gives the maximum subarray sum after applying the operation ; Function to return the maximum subarray sum after performing the given operation at most once ; If all element are negative then return the maximum element ; Maximum subarray sum without performing any operation ; Maximum subarray sum after performing the operations of first type ; Reversing the array to use the same existing function for operations of the second type ; Driver code
import java . util . * ; class GFG { static boolean areAllNegative ( int [ ] arr ) { int n = arr . length ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] > 0 ) return false ; } return true ; } static int [ ] getRightToLeftKadane ( int [ ] arr ) { int max_so_far = 0 , max_ending_here = 0 ; int size = arr . length ; int [ ] new_arr = new int [ size ] ; for ( int i = 0 ; i < size ; i ++ ) new_arr [ i ] = arr [ i ] ; for ( int i = size - 1 ; i >= 0 ; i -- ) { max_ending_here = max_ending_here + new_arr [ i ] ; if ( max_ending_here < 0 ) max_ending_here = 0 ; else if ( max_so_far < max_ending_here ) max_so_far = max_ending_here ; new_arr [ i ] = max_so_far ; } return new_arr ; } static int [ ] getPrefixSum ( int [ ] arr ) { int n = arr . length ; int [ ] new_arr = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) new_arr [ i ] = arr [ i ] ; for ( int i = 1 ; i < n ; i ++ ) new_arr [ i ] = new_arr [ i - 1 ] + new_arr [ i ] ; return new_arr ; } static int maxSumSubArr ( int [ ] a ) { int max_so_far = 0 , max_ending_here = 0 ; int n = a . length ; for ( int i = 0 ; i < n ; i ++ ) { max_ending_here = max_ending_here + a [ i ] ; if ( max_ending_here < 0 ) max_ending_here = 0 ; else if ( max_so_far < max_ending_here ) max_so_far = max_ending_here ; } return max_so_far ; } static int maxSumSubWithOp ( int [ ] arr ) { int [ ] kadane_r_to_l = getRightToLeftKadane ( arr ) ; int size = arr . length ; int [ ] prefixSum = getPrefixSum ( arr ) ; for ( int i = 1 ; i < size ; i ++ ) { prefixSum [ i ] = Math . max ( prefixSum [ i - 1 ] , prefixSum [ i ] ) ; } int max_subarray_sum = 0 ; for ( int i = 0 ; i < size - 1 ; i ++ ) { max_subarray_sum = Math . max ( max_subarray_sum , prefixSum [ i ] + kadane_r_to_l [ i + 1 ] ) ; } return max_subarray_sum ; } static int maxSum ( int [ ] arr , int size ) { if ( areAllNegative ( arr ) ) { int mx = - 1000000000 ; for ( int i = 0 ; i < size ; i ++ ) { if ( arr [ i ] > mx ) mx = arr [ i ] ; } return mx ; } int resSum = maxSumSubArr ( arr ) ; resSum = Math . max ( resSum , maxSumSubWithOp ( arr ) ) ; int [ ] reverse_arr = new int [ size ] ; for ( int i = 0 ; i < size ; i ++ ) reverse_arr [ size - 1 - i ] = arr [ i ] ; resSum = Math . max ( resSum , maxSumSubWithOp ( reverse_arr ) ) ; return resSum ; } public static void main ( String args [ ] ) { int [ ] arr = { - 9 , 21 , 24 , 24 , - 51 , - 6 , 17 , - 42 , - 39 , 33 } ; int size = arr . length ; System . out . println ( maxSum ( arr , size ) ) ; } }