C++で正確にk個の変更後に取得できる最大配列合計

正と負の整数の配列と数値Kが与えられます。タスクは、要素のKが変更された後の配列の最大合計を見つけることです。ここでの単一の変更操作は、単一の要素に-1を掛けます。

使用されるアプローチは、すべての負の数を正に変換することです。 N個の負の数がある場合、このために配列を並べ替えます-

• N

• K-Nがその場合でも、残りのK-N操作に対して符号を変更しても効果がない場合は、何もしません。

• K-Nが奇数の場合、残りのK-N演算では、最小数の符号を変更します（これは負になります）が、全体の合計は最大になります。

  または

  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）を使用して配列を並べ替えます

• ここで、最後のインデックスに到達するか、kが0になるまで、すべての負の要素に操作arr [i]*-1を適用します。

• kが負の要素の数よりも小さい場合、上記の手順でk-ve要素が変更されます。

• kが大きく、kの残りの値が奇数か偶数かがチェックされます。

• 残りのkが奇数の場合、操作arr [i] *-1を1回適用して最小要素の値を変更します。ここで、少なくともarr[i]が見つかります。 （-1奇数倍することは、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