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: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define right  2 NEW_LINE #define left  4 NEW_LINE int dp [ left ] [ right ] ; int findSubarraySum ( int ind , int flips , int n , int a [ ] , int k ) { if ( flips > k ) return -1e9 ; if ( ind == n ) return 0 ; if ( dp [ ind ] [ flips ] != -1 ) return dp [ ind ] [ flips ] ; int ans = 0 ; ans = max ( 0 , a [ ind ] + findSubarraySum ( ind + 1 , flips , n , a , k ) ) ; ans = max ( ans , - a [ ind ] + findSubarraySum ( ind + 1 , flips + 1 , n , a , k ) ) ; return dp [ ind ] [ flips ] = ans ; } int findMaxSubarraySum ( int a [ ] , int n , int k ) { memset ( dp , -1 , sizeof ( dp ) ) ; int ans = -1e9 ; for ( int i = 0 ; i < n ; i ++ ) ans = max ( ans , findSubarraySum ( i , 0 , n , a , k ) ) ; if ( ans == 0 && k == 0 ) return * max_element ( a , a + n ) ; return ans ; } int main ( ) { int a [ ] = { -1 , -2 , -100 , -10 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int k = 1 ; cout << findMaxSubarraySum ( a , n , k ) ; return 0 ; }