資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中K次取反後陣列和的最大值
問題陳述
給定一個大小為n的陣列和一個數字k。我們必須修改陣列k次。
修改陣列意味著在每次操作中，我們可以透過取反來替換任何陣列元素arr[i]，即arr[i] = -arr[i]。任務是以這樣的方式執行此操作，以便在k次操作後，陣列的和必須最大。
如果輸入arr[] = {7, -3, 5, 4, -1}，則最大和將為20
- 首先取反-3。現在陣列變為{7, 3, 5, 4, -1}
- 取反-1。現在陣列變為{7, 3, 5, 4, 1}
演算法
1. Replace the minimum element arr[i] in array by -arr[i] for current operation 2. Once minimum element becomes 0, we don’t need to make any more changes. In this way we can make sum of array maximum after K operations
示例
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n, int k){
for (int i = 1; i <= k; ++i) {
int minValue = INT_MAX;
int index = -1;
for (int j = 0; j < n; ++j) {
if (arr[j] < minValue) {
minValue = arr[j];
index = j;
}
}
if (minValue == 0) {
break;
}
arr[index] = -arr[index];
}
int sum = 0;
for (int i = 0; i < n; ++i) {
sum = sum + arr[i];
}
return sum;
}
int main(){
int arr[] = {7, -3, 5, 4, -1};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << "Maximum sum = " << getMaxSum(arr, n, k) << endl;
return 0;
}輸出
編譯並執行上述程式時，它會生成以下輸出：
Maximum sum = 20
更新於：2019年12月24日
305 次瀏覽
廣告