给定一个大小为n的数组和一个数字k。我们必须多次修改数组k。这里modify array意味着在每个操作中，我们可以用-arr[i]替换任何数组元素arr[i]。我们需要以这样一种方式执行这个操作，在K次操作之后，数组的和必须是最大的？
null
例如：
Input : arr[] = {-2, 0, 5, -1, 2} K = 4Output: 10Explanation:1. Replace (-2) by -(-2), array becomes {2, 0, 5, -1, 2}2. Replace (-1) by -(-1), array becomes {2, 0, 5, 1, 2}3. Replace (0) by -(0), array becomes {2, 0, 5, 1, 2}4. Replace (0) by -(0), array becomes {2, 0, 5, 1, 2}Input : arr[] = {9, 8, 8, 5} K = 3Output: 20
这个问题有着非常重要的意义 简单解决方案 ，对于当前操作，我们只需将数组中的最小元素arr[i]替换为-arr[i]。这样我们就可以在K次运算后使数组的和最大。一个有趣的例子是，一旦最小元素变为0，我们就不需要再做任何更改。
C++
// C++ program to maximize array sum after // k operations. #include <bits/stdc++.h> using namespace std; // This function does k operations on array // in a way that maximize the array sum. // index --> stores the index of current minimum // element for j'th operation int maximumSum( int arr[], int n, int k) { // Modify array K number of times for ( int i = 1; i <= k; i++) { int min = INT_MAX; int index = -1; // Find minimum element in array for // current operation and modify it // i.e; arr[j] --> -arr[j] for ( int j = 0; j < n; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } // this the condition if we find 0 as // minimum element, so it will useless to // replace 0 by -(0) for remaining operations if (min == 0) break ; // Modify element of array arr[index] = -arr[index]; } // Calculate sum of array int sum = 0; for ( int i = 0; i < n; i++) sum += arr[i]; return sum; } // Driver code int main() { int arr[] = { -2, 0, 5, -1, 2 }; int k = 4; int n = sizeof (arr) / sizeof (arr[0]); cout << maximumSum(arr, n, k); return 0; } |
JAVA
// Java program to maximize array // sum after k operations. class GFG { // This function does k operations // on array in a way that maximize // the array sum. index --> stores // the index of current minimum // element for j'th operation static int maximumSum( int arr[], int n, int k) { // Modify array K number of times for ( int i = 1 ; i <= k; i++) { int min = + 2147483647 ; int index = - 1 ; // Find minimum element in array for // current operation and modify it // i.e; arr[j] --> -arr[j] for ( int j = 0 ; j < n; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } // this the condition if we find 0 as // minimum element, so it will useless to // replace 0 by -(0) for remaining operations if (min == 0 ) break ; // Modify element of array arr[index] = -arr[index]; } // Calculate sum of array int sum = 0 ; for ( int i = 0 ; i < n; i++) sum += arr[i]; return sum; } // Driver code public static void main(String arg[]) { int arr[] = { - 2 , 0 , 5 , - 1 , 2 }; int k = 4 ; int n = arr.length; System.out.print(maximumSum(arr, n, k)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to maximize # array sum after k operations. # This function does k operations on array # in a way that maximize the array sum. # index --> stores the index of current # minimum element for j'th operation def maximumSum(arr, n, k): # Modify array K number of times for i in range ( 1 , k + 1 ): min = + 2147483647 index = - 1 # Find minimum element in array for # current operation and modify it # i.e; arr[j] --> -arr[j] for j in range (n): if (arr[j] < min ): min = arr[j] index = j # this the condition if we find 0 as # minimum element, so it will useless to # replace 0 by -(0) for remaining operations if ( min = = 0 ): break # Modify element of array arr[index] = - arr[index] # Calculate sum of array sum = 0 for i in range (n): sum + = arr[i] return sum # Driver code arr = [ - 2 , 0 , 5 , - 1 , 2 ] k = 4 n = len (arr) print (maximumSum(arr, n, k)) # This code is contributed by Anant Agarwal. |
C#
// C# program to maximize array // sum after k operations. using System; class GFG { // This function does k operations // on array in a way that maximize // the array sum. index --> stores // the index of current minimum // element for j'th operation static int maximumSum( int [] arr, int n, int k) { // Modify array K number of times for ( int i = 1; i <= k; i++) { int min = +2147483647; int index = -1; // Find minimum element in array for // current operation and modify it // i.e; arr[j] --> -arr[j] for ( int j = 0; j < n; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } // this the condition if we find // 0 as minimum element, so it // will useless to replace 0 by -(0) // for remaining operations if (min == 0) break ; // Modify element of array arr[index] = -arr[index]; } // Calculate sum of array int sum = 0; for ( int i = 0; i < n; i++) sum += arr[i]; return sum; } // Driver code public static void Main() { int [] arr = { -2, 0, 5, -1, 2 }; int k = 4; int n = arr.Length; Console.Write(maximumSum(arr, n, k)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP program to maximize // array sum after k operations. // This function does k operations // on array in a way that maximize // the array sum. index --> stores // the index of current minimum // element for j'th operation function maximumSum( $arr , $n , $k ) { $INT_MAX = 0; // Modify array K // number of times for ( $i = 1; $i <= $k ; $i ++) { $min = $INT_MAX ; $index = -1; // Find minimum element in // array for current operation // and modify it i.e; // arr[j] --> -arr[j] for ( $j = 0; $j < $n ; $j ++) { if ( $arr [ $j ] < $min ) { $min = $arr [ $j ]; $index = $j ; } } // this the condition if we // find 0 as minimum element, so // it will useless to replace 0 // by -(0) for remaining operations if ( $min == 0) break ; // Modify element of array $arr [ $index ] = - $arr [ $index ]; } // Calculate sum of array $sum = 0; for ( $i = 0; $i < $n ; $i ++) $sum += $arr [ $i ]; return $sum ; } // Driver Code $arr = array (-2, 0, 5, -1, 2); $k = 4; $n = sizeof( $arr ) / sizeof( $arr [0]); echo maximumSum( $arr , $n , $k ); // This code is contributed // by nitin mittal. ?> |
Javascript
<script> // Javascript program to maximize array // sum after k operations. // This function does k operations // on array in a way that maximize // the array sum. index --> stores // the index of current minimum // element for j'th operation function maximumSum(arr, n, k) { // Modify array K number of times for (let i = 1; i <= k; i++) { let min = +2147483647; let index = -1; // Find minimum element in array for // current operation and modify it // i.e; arr[j] --> -arr[j] for (let j = 0; j < n; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } // This the condition if we find 0 as // minimum element, so it will useless to // replace 0 by -(0) for remaining operations if (min == 0) break ; // Modify element of array arr[index] = -arr[index]; } // Calculate sum of array let sum = 0; for (let i = 0; i < n; i++) sum += arr[i]; return sum; } // Driver code let arr = [ -2, 0, 5, -1, 2 ]; let k = 4; let n = arr.length; document.write(maximumSum(arr, n, k)); // This code is contributed by code_hunt </script> |
输出
10
时间复杂性： O（k*n） 辅助空间： O（1）
- 方法2（使用排序）： 这种方法比上面讨论的方法要好一些。在这种方法中，我们将首先使用java内置的排序函数对给定数组进行排序，该函数的运行时复杂度最差为O（nlogn）。
- 然后，对于给定的k值，我们将继续遍历数组，直到k仍然大于0，如果数组在任何索引处的值小于0，我们将更改其符号，并将k减1。
- 如果我们在数组中找到一个0，我们会立即将k设置为0，以使结果最大化。
- 在某些情况下，如果数组中的所有值都大于0，我们将改变正值的符号，因为我们的数组已经排序，我们将改变数组中存在的较低值的符号，这将最终使我们的和最大化。
以下是上述方法的实施情况：
C++
// C++ program to find maximum array sum // after at most k negations. #include <bits/stdc++.h> using namespace std; int sol( int arr[], int n, int k) { int sum = 0; int i = 0; // Sorting given array using in-built // sort function sort(arr, arr + n); while (k > 0) { // If we find a 0 in our // sorted array, we stop if (arr[i] >= 0) k = 0; else { arr[i] = (-1) * arr[i]; k = k - 1; } i++; } // Calculating sum for ( int j = 0; j < n; j++) { sum += arr[j]; } return sum; } // Driver code int main() { int arr[] = { -2, 0, 5, -1, 2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << sol(arr, n, 4) << endl; return 0; } // This code is contributed by pratham76 |
JAVA
// Java program to find maximum array sum // after at most k negations. import java.util.Arrays; public class GFG { static int sol( int arr[], int k) { // Sorting given array using in-built // java sort function Arrays.sort(arr); int sum = 0 ; int i = 0 ; while (k > 0 ) { // If we find a 0 in our // sorted array, we stop if (arr[i] >= 0 ) k = 0 ; else { arr[i] = (- 1 ) * arr[i]; k = k - 1 ; } i++; } // Calculating sum for ( int j = 0 ; j < arr.length; j++) { sum += arr[j]; } return sum; } // Driver Code public static void main(String[] args) { int arr[] = { - 2 , 0 , 5 , - 1 , 2 }; System.out.println(sol(arr, 4 )); } } |
Python3
# Python3 program to find maximum array # sum after at most k negations def sol(arr, k): # Sorting given array using # in-built java sort function arr.sort() Sum = 0 i = 0 while (k > 0 ): # If we find a 0 in our # sorted array, we stop if (arr[i] > = 0 ): k = 0 else : arr[i] = ( - 1 ) * arr[i] k = k - 1 i + = 1 # Calculating sum for j in range ( len (arr)): Sum + = arr[j] return Sum # Driver code arr = [ - 2 , 0 , 5 , - 1 , 2 ] print (sol(arr, 4 )) # This code is contributed by avanitrachhadiya2155 |
C#
// C# program to find maximum array sum // after at most k negations. using System; class GFG{ static int sol( int []arr, int k) { // Sorting given array using // in-built java sort function Array.Sort(arr); int sum = 0; int i = 0; while (k > 0) { // If we find a 0 in our // sorted array, we stop if (arr[i] >= 0) k = 0; else { arr[i] = (-1) * arr[i]; k = k - 1; } i++; } // Calculating sum for ( int j = 0; j < arr.Length; j++) { sum += arr[j]; } return sum; } // Driver code public static void Main( string [] args) { int []arr = { -2, 0, 5, -1, 2 }; Console.Write(sol(arr, 4)); } } // This code is contributed by rutvik_56 |
Javascript
<script> // JavaScript program to find maximum array sum // after at most k negations. function sol(arr, k) { // Sorting given array using in-built // java sort function arr.sort(); let sum = 0; let i = 0; while (k > 0) { // If we find a 0 in our // sorted array, we stop if (arr[i] >= 0) k = 0; else { arr[i] = (-1) * arr[i]; k = k - 1; } i++; } // Calculating sum for (let j = 0; j < arr.length; j++) { sum += arr[j]; } return sum; } // Driver code let arr = [ -2, 0, 5, -1, 2 ]; document.write(sol(arr, 4)); // This code is contributed by souravghosh0416. </script> |
输出
10
时间复杂性： O（n*logn） 辅助空间： O（1）
方法3（使用排序）：
当需要否定最多k个元素时，上述方法2是最佳的。为了解决当存在正k个否定时的问题，下面给出了算法。
- 按升序对数组排序。初始化i=0。
- 增加i，将所有负元素乘以-1，直到k变为或达到正元素。
- 检查数组是否已结束。如果为真，则转到第（n-1）个元素。
- 如果k==0或k为偶数，则返回所有元素的和。否则，将第i个或（i-1）个元素的最小值的绝对值乘以-1。
- 返回数组的和。
以下是上述方法的实施情况：
C++
// C++ program for the above approach #include <algorithm> #include <iostream> using namespace std; // Function to calculate sum of the array long long int sumArray( long long int * arr, int n) { long long int sum = 0; // Iterate from 0 to n - 1 for ( int i = 0; i < n; i++) { sum += arr[i]; } return sum; } // Function to maximize sum long long int maximizeSum( long long int arr[], int n, int k) { sort(arr, arr + n); int i = 0; // Iterate from 0 to n - 1 for (i = 0; i < n; i++) { if (k && arr[i] < 0) { arr[i] *= -1; k--; continue ; } break ; } if (i == n) i--; if (k == 0 || k % 2 == 0) { return sumArray(arr, n); } if (i != 0 && abs (arr[i]) >= abs (arr[i - 1])) { i--; } arr[i] *= -1; return sumArray(arr, n); } // Driver Code int main() { int n = 5; int k = 4; long long int arr[5] = { -3, -2, -1, 5, 6 }; // Function Call cout << maximizeSum(arr, n, k) << endl; return 0; } |
JAVA
// Java program for the above approach import java.util.*; class GFG{ // Function to calculate sum of the array static int sumArray( int [] arr, int n) { int sum = 0 ; // Iterate from 0 to n - 1 for ( int i = 0 ; i < n; i++) { sum += arr[i]; } return sum; } // Function to maximize sum static int maximizeSum( int arr[], int n, int k) { Arrays.sort(arr); int i = 0 ; // Iterate from 0 to n - 1 for (i = 0 ; i < n; i++) { if (k != 0 && arr[i] < 0 ) { arr[i] *= - 1 ; k--; continue ; } break ; } if (i == n) i--; if (k == 0 || k % 2 == 0 ) { return sumArray(arr, n); } if (i != 0 && Math.abs(arr[i]) >= Math.abs(arr[i - 1 ])) { i--; } arr[i] *= - 1 ; return sumArray(arr, n); } // Driver Code public static void main(String args[]) { int n = 5 ; int k = 4 ; int arr[] = { - 3 , - 2 , - 1 , 5 , 6 }; // Function Call System.out.print(maximizeSum(arr, n, k)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to calculate sum of the array def sumArray(arr, n): sum = 0 # Iterate from 0 to n - 1 for i in range (n): sum + = arr[i] return sum # Function to maximize sum def maximizeSum(arr, n, k): arr.sort() i = 0 # Iterate from 0 to n - 1 for i in range (n): if (k and arr[i] < 0 ): arr[i] * = - 1 k - = 1 continue break if (i = = n): i - = 1 if (k = = 0 or k % 2 = = 0 ): return sumArray(arr, n) if (i ! = 0 and abs (arr[i]) > = abs (arr[i - 1 ])): i - = 1 arr[i] * = - 1 return sumArray(arr, n) # Driver Code n = 5 k = 4 arr = [ - 3 , - 2 , - 1 , 5 , 6 ] # Function Call print (maximizeSum(arr, n, k)) # This code is contributed by rohitsingh07052 |
C#
// C# program for the above approach using System; class GFG{ // Function to calculate sum of the array static int sumArray( int [] arr, int n) { int sum = 0; // Iterate from 0 to n - 1 for ( int i = 0; i < n; i++) { sum += arr[i]; } return sum; } // Function to maximize sum static int maximizeSum( int [] arr, int n, int k) { Array.Sort(arr); int i = 0; // Iterate from 0 to n - 1 for (i = 0; i < n; i++) { if (k != 0 && arr[i] < 0) { arr[i] *= -1; k--; continue ; } break ; } if (i == n) i--; if (k == 0 || k % 2 == 0) { return sumArray(arr, n); } if (i != 0 && Math.Abs(arr[i]) >= Math.Abs(arr[i - 1])) { i--; } arr[i] *= -1; return sumArray(arr, n); } // Driver Code static public void Main() { int n = 5; int k = 4; int [] arr = { -3, -2, -1, 5, 6 }; // Function Call Console.Write(maximizeSum(arr, n, k)); } } // This code is contributed by shubhamsingh10 |
Javascript
<script> // Javascript program for the above approach // Function to calculate sum of the array function sumArray(arr,n) { let sum = 0; // Iterate from 0 to n - 1 for (let i = 0; i < n; i++) { sum += arr[i]; } return sum; } // Function to maximize sum function maximizeSum(arr,n,k) { (arr).sort( function (a,b){ return a-b;}); let i = 0; // Iterate from 0 to n - 1 for (i = 0; i < n; i++) { if (k != 0 && arr[i] < 0) { arr[i] *= -1; k--; continue ; } break ; } if (i == n) i--; if (k == 0 || k % 2 == 0) { return sumArray(arr, n); } if (i != 0 && Math.abs(arr[i]) >= Math.abs(arr[i - 1])) { i--; } arr[i] *= -1; return sumArray(arr, n); } // Driver Code let n = 5; let k = 4; let arr=[-3, -2, -1, 5, 6 ]; // Function Call document.write(maximizeSum(arr, n, k)); // This code is contributed by ab2127 </script> |
输出
15
时间复杂性： O（n*logn）
辅助空间： O（1）
本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
