Given an array arr[] of N integers and an integer K, The task is to find the maximum sub-array sum by flipping signs of at most K array elements.
Examples:
Input: arr[] = {-6, 2, -1, -1000, 2}, k = 2
Output: 1009
We can flip the signs of -6 and -1000, to get maximum subarray sum as 1009Input: arr[] = {-1, -2, -100, -10}, k = 1
Output: 100
We can only flip the sign of -100 to get 100Input: {1, 2, 100, 10}, k = 1
Output: 113
We do not need to flip any elements
Approach: The problem can be solved using Dynamic Programming. Let dp[i][j] be the maximum sub-array sum from index i with j flips. A recursive function can be written in order to solve the problem and we can use memoization to avoid multiple function calls. The recursive DP function (findSubarraySum(ind, flips)) will be called from every index with the number of initial flips as 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))
If the value is negative, we are replacing it by 0, similarly as we do in Kadane’s algorithm.
The recursive function will have two states, one will be if we flip the i-th index. The second one is if we don’t flip the i-th index. The base cases are if the ind==n when we have completed a traversal till the last index. We can use memoization in order to store the results which can be used later to avoid multiple same-function calls. The maximum of all dp[i][0] will be our answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define right 2#define left 4int dp[left][right];// Function to find the maximum subarray sum with flips// starting from index iint findSubarraySum(int ind, int flips, int n, int a[], int k){ // If the number of flips have exceeded if (flips > k) return -1e9; // Complete traversal if (ind == n) return 0; // If the state has previously been visited if (dp[ind][flips] != -1) return dp[ind][flips]; // Initially int ans = 0; // Use Kadane's algorithm and call two states 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)); // Memoize the answer and return it return dp[ind][flips] = ans;}// Utility function to call flips from index and// return the answerint findMaxSubarraySum(int a[], int n, int k){ // Create DP array // int dp[n][k+1]; memset(dp, -1, sizeof(dp)); int ans = -1e9; // Iterate and call recursive function // from every index to get the maximum subarray sum for (int i = 0; i < n; i++) ans = max(ans, findSubarraySum(i, 0, n, a, k)); // corner case if (ans == 0 && k == 0) return *max_element(a, a + n); return ans;}// Driver Codeint main(){ int a[] = { -1, -2, -100, -10 }; int n = sizeof(a) / sizeof(a[0]); int k = 1; cout << findMaxSubarraySum(a, n, k); return 0;} |
Java
// Java implementation of the approachimport java.util.Arrays;class GFG { static int right = 2; static int left = 4; static int[][] dp = new int[left][right]; // Function to find the maximum subarray sum with flips // starting from index i static int findSubarraySum(int ind, int flips, int n, int[] a, int k) { // If the number of flips have exceeded if (flips > k) return (int)(-1e9); // Complete traversal if (ind == n) return 0; // If the state has previously been visited if (dp[ind][flips] != -1) return dp[ind][flips]; // Initially int ans = 0; // Use Kadane's algorithm and call two states 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)); // Memoize the answer and return it return dp[ind][flips] = ans; } // Utility function to call flips from index and // return the answer static int findMaxSubarraySum(int[] a, int n, int k) { // Create DP array // int dp[n,k+1]; for (int i = 0; i < n; i++) for (int j = 0; j < k + 1; j++) dp[i][j] = -1; int ans = (int)(-1e9); // Iterate and call recursive function // from every index to get the maximum subarray sum for (int i = 0; i < n; i++) ans = Math.max(ans, findSubarraySum(i, 0, n, a, k)); // corner case if (ans == 0 && k == 0) return Arrays.stream(a).max().getAsInt(); return ans; } // Driver Code 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)); }}// This code is contributed by mits |
Python3
# Python3 implementation of the approach import numpy as npright = 3; left = 6; dp = np.ones((left, right))dp = -1 * dp# Function to find the maximum # subarray sum with flips starting # from index i def findSubarraySum(ind, flips, n, a, k) : # If the number of flips # have exceeded if (flips > k) : return -1e9; # Complete traversal if (ind == n) : return 0; # If the state has previously # been visited if (dp[ind][flips] != -1) : return dp[ind][flips]; # Initially ans = 0; # Use Kadane's algorithm and # call two states 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)); # Memoize the answer and return it dp[ind][flips] = ans; return dp[ind][flips] ;# Utility function to call flips # from index and return the answer def findMaxSubarraySum(a, n, k) : ans = -1e9; # Iterate and call recursive # function from every index to # get the maximum subarray sum for i in range(n) : ans = max(ans, findSubarraySum(i, 0, n, a, k)); # corner casae if ans == 0 and k == 0: return max(a); return ans; # Driver Code if __name__ == "__main__" : a = [-1, -2, -100, -10]; n = len(a) ; k = 1; print(findMaxSubarraySum(a, n, k)); # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;using System.Linq;class GFG { static int right = 2; static int left = 4; static int[, ] dp = new int[left + 1, right + 1]; // Function to find the maximum subarray sum // with flips starting from index i static int findSubarraySum(int ind, int flips, int n, int[] a, int k) { // If the number of flips have exceeded if (flips > k) return -(int)1e9; // Complete traversal if (ind == n) return 0; // If the state has previously been visited if (dp[ind, flips] != -1) return dp[ind, flips]; // Initially int ans = 0; // Use Kadane's algorithm and call two states 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)); // Memoize the answer and return it return dp[ind, flips] = ans; } // Utility function to call flips from // index and return the answer static int findMaxSubarraySum(int[] a, int n, int k) { // Create DP array // int dp[n][k+1]; for (int i = 0; i < n; i++) for (int j = 0; j < k + 1; j++) dp[i, j] = -1; int ans = -(int)1e9; // Iterate and call recursive function // from every index to get the maximum subarray sum for (int i = 0; i < n; i++) ans = Math.Max(ans, findSubarraySum(i, 0, n, a, k)); // corner case if (ans == 0 && k == 0) return a.Max(); return ans; } // Driver Code static void Main() { int[] a = { -1, -2, -100, -10 }; int n = a.Length; int k = 1; Console.WriteLine(findMaxSubarraySum(a, n, k)); }}// This code is contributed by mits |
Javascript
<script> // Javascript implementation of the approach let right = 2; let left = 4; let dp = new Array(left); // Function to find the maximum subarray sum with flips // starting from index i function findSubarraySum(ind, flips, n, a, k) { // If the number of flips have exceeded if (flips > k) return (-1e9); // Complete traversal if (ind == n) return 0; // If the state has previously been visited if (dp[ind][flips] != -1) return dp[ind][flips]; // Initially let ans = 0; // Use Kadane's algorithm and call two states 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)); // Memoize the answer and return it return dp[ind][flips] = ans; } // Utility function to call flips from index and // return the answer function findMaxSubarraySum(a, n, k) { // Create DP array // int dp[n,k+1]; 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); // Iterate and call recursive function // from every index to get the maximum subarray sum for (let i = 0; i < n; i++) ans = Math.max(ans, findSubarraySum(i, 0, n, a, k)); // corner case 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)); </script> |
100
Time Complexity: O(N * K), as we are using a loop to traverse N times and we are recursively calling the function K times which will cost O(K). Where N is the number of elements in the array and K is the limit of elements.
Auxiliary Space: O(N * K), as we are using extra space for memorization. Where N is the number of elements in the array and K is the limit of elements.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
