Dada una array arr , la tarea es encontrar la suma máxima de la subsecuencia después de cambiar los signos de como máximo K elementos.
Ejemplos:
Entrada : arr = [6, -10, -1, 0, -4, 2], K = 2
Salida : 22
Explicación : la suma máxima se puede obtener cambiando -10 y -4 a 10 y 4 respectivamenteEntrada : arr = [1, 2, 3], K = 3
Salida : 6
Enfoque : siga los pasos a continuación para resolver el problema:
- Ordenar la array
- Inicialice una suma variable a 0 para almacenar la suma máxima de la subsecuencia
- Iterar la array y convertir elementos negativos en positivos y disminuir k hasta k > 0
- Atraviese la array y agregue solo valores positivos a la suma
- Devuelve la suma de la respuesta
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
22
Complejidad temporal: O(N)
Espacio auxiliar: O(1)