資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中利用給定操作最大化陣列和
描述
有一個包含(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
更新於：2019-12-31
130 次瀏覽
廣告