我们给了一个带有正负整数的数组以及一个数字K。任务是在元素的K更改后找到该数组的最大和。单个更改操作在此将单个元素乘以-1。
使用的方法是将每个负数转换为正数。如果有N个负数,那么为此我们将对数组进行排序-
如果N <K,则在执行N次运算后,每个元素都是正数,剩下的就是KN次运算
现在,如果KN变为偶数,那么对于其余的KN操作,更改符号将无效,则不执行任何操作。
如果KN为奇数,则对于其余的KN操作,请更改最小数的符号(它将变为负数),但总和将为最大。
要么
如果N> K,则更改K个负数的符号并添加数组。总和为最大。
Arr[]= { 0,-2,6,4,8,2,-3 } K=4
输出结果
Maximum array sum is : 25
说明-元素的4个变化是
1. 0,2,6,4,8,2,-3 -2 changed to 2 2. 0,2,6,4,8,2,3 -3 changed to 3 3. 0,-2,6,4,8,2,3 2 changed to -2 4. 0,2,6,4,8,2,3 -2 changed to 2 Maximum sum is 25
Arr[]= { -1,-2,-3,-4,-5,-6,-7 } K=4
输出结果
Maximum array sum is : 16
说明-元素的4个变化是
1. -1,-2,-3,-4,-5,-6,7 -7 changed to 7 2. -1,-2,-3,-4,-5,6,7 -6 changed to 6 3. -1,-2,-3,-4,5,6,7 -5 changed to 5 4. -1,-2,-3,4,5,6,7 -4 changed to 4 Maximum sum is 16
整数数组Arr []用于存储整数。
整数“大小”存储数组的长度,并初始化K。
函数returnSum(int arr [],int n,int k)将数组,数组的大小和k作为输入,并在精确地执行k次操作后返回其元素的最大和。
首先,我们将使用sort(arr,arr + n)对数组进行排序
现在,我们将对所有否定元素应用操作arr [i] *-1,直到到达最后一个索引或k变为0。
如果k小于负数元素的数量,则上述步骤将更改k-ve个元素。
如果k较大,则将检查k的剩余值是否为奇数或偶数。
如果剩余的k是奇数,那么我们将通过应用arr [i] *-1一次来更改最小元素的值,其中至少找到arr [i]。(乘以-1的奇数倍等于一次)
如果剩余k为偶数,则arr [i] *-1将无效。没做什么。
计算整个数组的总和并返回结果。
#include <bits/stdc++.h> using namespace std; int returnSum(int arr[], int n, int k){ // Sort the array elements sort(arr, arr + n); // Change signs of the negative elements // starting from the smallest //this loop will change the sign of -ve elements //for each k one -ve element is turned positive for(i=0;i<n;i++) if(k>0 && arr[i]<0){ arr[i]=arr[i]*-1; k--; } //if k is non zero and odd change sign of minimum element //once as it is same as changing its sign odd times if (k % 2 == 1) { int min = arr[0]; int pos=0; //index of minimum element for (i = 1; i < n; i++) if (arr[i]<min){ min = arr[i]; pos=i; } arr[pos] *= -1; } int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; return sum; } int main(){ int Arr[] = { -3, 4, -3, 6, 8 }; int size =5; int K = 4; cout <<"Maximum array sum that can be obtained after exactly k changes" returnSum(Arr, size, K) << endl; return 0; }
输出结果
Maximum array sum that can be obtained after exactly k changes : 24