Maximum subarray sum by flipping signs of at most K array elements | Java implementation of the approach ; Function to find the maximum subarray sum with flips starting from index i ; If the number of flips have exceeded ; Complete traversal ; If the state has previously been visited ; Initially ; Use Kadane 's algorithm and call two states ; Memoize the answer and return it ; Utility function to call flips from index and return the answer ; Create DP array int dp [ n , k + 1 ] ; ; Iterate and call recursive function from every index to get the maximum subarray sum ; corner case ; Driver Code
import java . util . Arrays ; class GFG { static int right = 2 ; static int left = 4 ; static int [ ] [ ] dp = new int [ left ] [ right ] ; static int findSubarraySum ( int ind , int flips , int n , int [ ] a , int k ) { if ( flips > k ) return ( int ) ( - 1e9 ) ; if ( ind == n ) return 0 ; if ( dp [ ind ] [ flips ] != - 1 ) return dp [ ind ] [ flips ] ; int ans = 0 ; ans = Math . max ( 0 , a [ ind ] + findSubarraySum ( ind + 1 , flips , n , a , k ) ) ; ans = Math . max ( ans , - a [ ind ] + findSubarraySum ( ind + 1 , flips + 1 , n , a , k ) ) ; return dp [ ind ] [ flips ] = ans ; } static int findMaxSubarraySum ( int [ ] a , int n , int k ) { for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < k + 1 ; j ++ ) dp [ i ] [ j ] = - 1 ; int ans = ( int ) ( - 1e9 ) ; for ( int i = 0 ; i < n ; i ++ ) ans = Math . max ( ans , findSubarraySum ( i , 0 , n , a , k ) ) ; if ( ans == 0 && k == 0 ) return Arrays . stream ( a ) . max ( ) . getAsInt ( ) ; return ans ; } public static void main ( String [ ] args ) { int [ ] a = { - 1 , - 2 , - 100 , - 10 } ; int n = a . length ; int k = 1 ; System . out . println ( findMaxSubarraySum ( a , n , k ) ) ; } }