資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中獲取恰好 k 次更改後最大陣列和
給定一個包含正整數和負整數的陣列以及一個數字 K。任務是在對陣列元素進行恰好 K 次更改後找到陣列的最大和。這裡的單次更改操作將單個元素乘以 -1。
使用的方法是將每個負數轉換為正數。如果存在 N 個負數，則為此我們將對陣列進行排序：
如果 N<K，則在 N 次操作後每個元素都將為正，並且我們剩下 K-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[] 用於儲存整數。
整數“size”儲存陣列的長度，並初始化 K。
函式 returnSum( int arr[], int n, int k) 以陣列、其大小和 k 作為輸入，並在恰好進行 k 次操作後返回其元素的最大和。
首先，我們將使用 sort(arr,arr+n) 對陣列進行排序
現在，我們將對所有負元素應用操作 arr[i]*-1，直到到達最後一個索引或 k 變為 0。
如果 k 小於負元素的數量，則上述步驟將更改 k 個負元素。
如果 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
更新於：2020-07-28
615 次檢視
廣告