설명
(2 * n – 1)개의 정수 배열이 있습니다. 배열에서 정확히 n개 요소의 부호를 변경할 수 있습니다. 즉, 정확히 n개의 배열 요소를 선택하고 각각에 -1을 곱할 수 있습니다. 배열의 최대 합을 찾습니다.
예시
입력 배열이 {-2, 100, -3}이면 -2와 -3의 최대 변화 부호를 얻을 수 있습니다. 부호 배열을 변경하면 -
가 됩니다.{2, 100, 3}이고 이 배열의 최대 합은 105입니다.
알고리즘
- 음수 계산
- 숫자의 절대값을 취하여 배열의 합을 계산합니다.
- 숫자의 절대값을 취하여 배열의 최소값 찾기
- 아니오인지 확인하십시오. 음수의 값은 홀수이고 n의 값은 짝수이며 합계에서 m의 두 배를 빼면 이것이 배열의 최대 합이 됩니다. 그렇지 않으면 합계의 값은 배열의 최대 합이 됩니다.
- 위의 단계를 (2 * n – 1)번 반복
예시
이제 예를 살펴보겠습니다 -
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
int negtiveCnt = 0;
int sum = 0;
int m = INT_MAX;
for (int i = 0; i < 2 * n - 1; ++i) {
if (arr[i] < 0) {
++negtiveCnt;
}
sum = sum + abs(arr[i]);
m = min(m, abs(arr[i]));
}
if (negtiveCnt % 2 && n % 2 == 0) {
sum = sum - 2 * m;
return sum;
}
return sum;
}
int main() {
int arr[] = {-2, 100, -3};
int n = 2;
cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
return 0;
} 출력
Maximum sum = 105