Find maximum sum of subsequence after flipping signs of at most K elements in given Array
Given an array arr, the task is to find the maximum sum of subsequence after flipping signs of at most K elements.
Examples:
Input: arr = [6, -10, -1, 0, -4, 2], K = 2
Output: 22
Explanation: Maximum sum can be obtained by flipping -10 and -4 to 10 and 4 respectivelyInput: arr = [1, 2, 3], K = 3
Output: 6
Approach: Follow the steps below to solve the problem:
- Sort the array
- Initialize a variable sum to 0 to store the maximum sum of subsequence
- Iterate the array and convert negative elements to positive and decrement k until k > 0
- Traverse the array and add only positive values to sum
- Return the answer sum
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate // the max sum of subsequence int maxSubseq( int arr[], int N, int K) { // Variable to store the max sum int sum = 0; // Sort the array sort(arr, arr + N); // Iterate over the array for ( int i = 0; i < N; i++) { if (K == 0) break ; if (arr[i] < 0) { // Flip sign arr[i] = -arr[i]; // Decrement k K--; } } // Traverse over the array for ( int i = 0; i < N; i++) // Add only positive elements if (arr[i] > 0) sum += arr[i]; // Return the max sum return sum; } // Driver Code int main() { // Given array int arr[] = { 6, -10, -1, 0, -4, 2 }; // Variable to store number // of flips are allowed int K = 2; int N = sizeof (arr) / sizeof (arr[0]); // Function call to find // the maximum sum of subsequence cout << maxSubseq(arr, N, K); return 0; } |
Java
// Java implementation for the above approach import java.util.*; class GFG { // Function to calculate // the max sum of subsequence static int maxSubseq( int arr[], int N, int K) { // Variable to store the max sum int sum = 0 ; // Sort the array Arrays.sort(arr); // Iterate over the array for ( int i = 0 ; i < N; i++) { if (K == 0 ) break ; if (arr[i] < 0 ) { // Flip sign arr[i] = -arr[i]; // Decrement k K--; } } // Traverse over the array for ( int i = 0 ; i < N; i++) // Add only positive elements if (arr[i] > 0 ) sum += arr[i]; // Return the max sum return sum; } // Driver Code public static void main(String []args) { // Given array int []arr = { 6 , - 10 , - 1 , 0 , - 4 , 2 }; // Variable to store number // of flips are allowed int K = 2 ; int N = arr.length; // Function call to find // the maximum sum of subsequence System.out.println(maxSubseq(arr, N, K)); } } // This code is contributed by ipg2016107. |
Python3
# Python 3 implementation for the above approach # Function to calculate # the max sum of subsequence def maxSubseq(arr, N, K): # Variable to store the max sum sum = 0 # Sort the array arr.sort() # Iterate over the array for i in range (N): if (K = = 0 ): break if (arr[i] < 0 ): # Flip sign arr[i] = - arr[i] # Decrement k K - = 1 # Traverse over the array for i in range (N): # Add only positive elements if (arr[i] > 0 ): sum + = arr[i] # Return the max sum return sum # Driver Code if __name__ = = "__main__" : # Given array arr = [ 6 , - 10 , - 1 , 0 , - 4 , 2 ] # Variable to store number # of flips are allowed K = 2 N = len (arr) # Function call to find # the maximum sum of subsequence print (maxSubseq(arr, N, K)) # This code is contributed by ukasp. |
C#
// C++ implementation for the above approach using System; class GFG { // Function to calculate // the max sum of subsequence static int maxSubseq( int []arr, int N, int K) { // Variable to store the max sum int sum = 0; // Sort the array Array.Sort(arr); // Iterate over the array for ( int i = 0; i < N; i++) { if (K == 0) break ; if (arr[i] < 0) { // Flip sign arr[i] = -arr[i]; // Decrement k K--; } } // Traverse over the array for ( int i = 0; i < N; i++) // Add only positive elements if (arr[i] > 0) sum += arr[i]; // Return the max sum return sum; } // Driver Code public static void Main( string [] args) { // Given array int []arr = { 6, -10, -1, 0, -4, 2 }; // Variable to store number // of flips are allowed int K = 2; int N = arr.Length; // Function call to find // the maximum sum of subsequence Console.Write(maxSubseq(arr, N, K)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript implementation for the above approach // Function to calculate // the max sum of subsequence const maxSubseq = (arr, N, K) => { // Variable to store the max sum let sum = 0; // Sort the array arr.sort((a, b) => a - b); // Iterate over the array for (let i = 0; i < N; i++) { if (K == 0) break ; if (arr[i] < 0) { // Flip sign arr[i] = -arr[i]; // Decrement k K--; } } // Traverse over the array for (let i = 0; i < N; i++) // Add only positive elements if (arr[i] > 0) sum += arr[i]; // Return the max sum return sum; } // Driver Code // Given array let arr = [6, -10, -1, 0, -4, 2]; // Variable to store number // of flips are allowed let K = 2; let N = arr.length // Function call to find // the maximum sum of subsequence document.write(maxSubseq(arr, N, K)); // This code is contributed by rakeshsahni </script> |
Output:
22
Time Complexity: O(N*log2N) since sort() has been called. Here, N is size of input array.
Auxiliary Space: O(1)