Maximum sum subarray after altering the array | Java implementation of the approach ; Function to return the maximum subarray sum ; Function to reverse the subarray arr [ 0. . . i ] ; Function to return the maximum subarray sum after performing the given operation at most once ; To store the result ; When no operation is performed ; Find the maximum subarray sum after reversing the subarray arr [ 0. . . i ] for all possible values of i ; The complete array is reversed so that the subarray can be processed as arr [ 0. . . i ] instead of arr [ i ... N - 1 ] ; Driver code
import java . util . * ; class GFG { static int maxSumSubarray ( int [ ] arr , int size ) { int max_so_far = Integer . MIN_VALUE , max_ending_here = 0 ; for ( int i = 0 ; i < size ; i ++ ) { max_ending_here = max_ending_here + arr [ i ] ; if ( max_so_far < max_ending_here ) max_so_far = max_ending_here ; if ( max_ending_here < 0 ) max_ending_here = 0 ; } return max_so_far ; } static void getUpdatedArray ( int [ ] arr , int [ ] copy , int i ) { for ( int j = 0 ; j <= ( i / 2 ) ; j ++ ) { copy [ j ] = arr [ i - j ] ; copy [ i - j ] = arr [ j ] ; } return ; } static int [ ] reverse ( int a [ ] ) { int i , n = a . length , t ; for ( i = 0 ; i < n / 2 ; i ++ ) { t = a [ i ] ; a [ i ] = a [ n - i - 1 ] ; a [ n - i - 1 ] = t ; } return a ; } static int maxSum ( int [ ] arr , int size ) { int resSum = Integer . MIN_VALUE ; resSum = Math . max ( resSum , maxSumSubarray ( arr , size ) ) ; int [ ] copyArr = arr ; for ( int i = 1 ; i < size ; i ++ ) { getUpdatedArray ( arr , copyArr , i ) ; resSum = Math . max ( resSum , maxSumSubarray ( copyArr , size ) ) ; } arr = reverse ( arr ) ; copyArr = arr ; for ( int i = 1 ; i < size ; i ++ ) { getUpdatedArray ( arr , copyArr , i ) ; resSum = Math . max ( resSum , maxSumSubarray ( copyArr , size ) ) ; } resSum += 6 ; 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 . print ( maxSum ( arr , size ) ) ; } }