Maximum subarray sum by flipping signs of at most K array elements | Javascript 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
let right = 2 ; let left = 4 ; let dp = new Array ( left ) ; function findSubarraySum ( ind , flips , n , a , k ) { if ( flips > k ) return ( - 1e9 ) ; if ( ind == n ) return 0 ; if ( dp [ ind ] [ flips ] != - 1 ) return dp [ ind ] [ flips ] ; let 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 ; } function findMaxSubarraySum ( a , n , k ) { for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = new Array ( k ) ; for ( let j = 0 ; j < k + 1 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } let ans = ( - 1e9 ) ; for ( let i = 0 ; i < n ; i ++ ) ans = Math . max ( ans , findSubarraySum ( i , 0 , n , a , k ) ) ; if ( ans == 0 && k == 0 ) { let max = Number . MIN_VALUE ; for ( let i = 0 ; i < a . length ; i ++ ) { max = Math . max ( max , a [ i ] ) ; } return max ; } return ans ; } let a = [ - 1 , - 2 , - 100 , - 10 ] ; let n = a . length ; let k = 1 ; document . write ( findMaxSubarraySum ( a , n , k ) ) ;