양수 및 음수 정수 배열과 숫자 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]가 있는 곳에서 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