text: Maximum subarray sum by flipping signs of at most K array elements | C # 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
code: using System ; using System . Linq ; class GFG { static int right = 2 ; static int left = 4 ; static int [ , ] dp = new int [ left + 1 , right + 1 ] ; 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 a . Max ( ) ; return ans ; } static void Main ( ) { int [ ] a = { - 1 , - 2 , - 100 , - 10 } ; int n = a . Length ; int k = 1 ; Console . WriteLine ( findMaxSubarraySum ( a , n , k ) ) ; } }