Maximum subarray sum with same first and last element formed by removing elements | Java program for the above approach ; Function to find the maximum sum of sub - array ; Initialize the variables ; Traverse over the range ; Add the current value to the variable currsum for prefix sum ; Calculate the result ; Return the answer ; Driver Code
import java . io . * ; import java . util . * ; class GFG { static int maximumSubarraySum ( int arr [ ] , int N ) { HashMap < Integer , Integer > memo = new HashMap < > ( ) ; int res = Integer . MIN_VALUE ; int currsum = 0 , currval = 0 ; for ( int i = 0 ; i < N ; ++ i ) { currval = arr [ i ] ; currsum = currsum + currval ; if ( memo . containsKey ( currval ) ) { if ( currval > 0 ) res = Math . max ( res , currsum - memo . get ( currval ) + currval ) ; else res = Math . max ( res , currsum - memo . get ( currval ) + 2 * currval ) ; } else memo . put ( currval , currsum ) ; if ( currval < 0 ) currsum = currsum - currval ; } return res ; } public static void main ( String [ ] args ) { int arr [ ] = { - 1 , - 3 , 4 , 0 , - 1 , - 2 } ; int N = 6 ; System . out . println ( maximumSubarraySum ( arr , N ) ) ; } }