在C ++中精确地进行k次更改后可获得的最大数组和

我们给了一个带有正负整数的数组以及一个数字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