資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中透過乘以陣列字首乘以-1來最大化陣列的和
給定一個整數陣列，任務是首先獲取陣列的字首，然後將其乘以 -1，其次計算陣列的字首和，最後從生成的字首陣列中找到最大和。
字首陣列生成方式如下：
字首陣列 `prefixArray[0]` 的第一個元素 = 陣列的第一個元素
字首陣列 `prefixArray[1]` 的第二個元素 = `prefixArray[0]` + `arr[1]`
字首陣列 `prefixArray[2]` 的第三個元素 = `prefixArray[1]` + `arr[2]`
字首陣列 `prefixArray[3]` 的第四個元素 = `prefixArray[2]` + `arr[3]`……等等。
讓我們看看各種輸入輸出場景：
輸入 - `int arr[] = {2, 4, 1, 5, 2}`
輸出 - 字首陣列是：-2 2 3 8 10 透過將陣列字首乘以 -1 來最大化陣列的和是：21
解釋 - 給定一個整數陣列。首先獲取陣列的字首 2 並將其乘以 -1。因此，新陣列將是 {-2, 4, 1, 5, 2}。現在，我們將形成字首陣列 {-2, 2, 3, 8, 10}。最後一步是最大化和，即 -2 + 2 + 3 + 8 + 10 = 21，這是最終輸出。
輸入 - `int arr[] = {-1, 4, 2, 1, -9, 6};`
輸出 - 字首陣列是：1 5 7 8 -1 5 透過將陣列字首乘以 -1 來最大化陣列的和是：19
解釋 - 給定一個整數陣列。首先獲取陣列的字首 -1 並將其乘以 -1。因此，新陣列將是 {1, 4, 2, 1, -9, 6}。現在，我們將形成字首陣列 {1, 5, 7, 8, -1, 5}。最後一步是最大化和，即 1 + 5 + 7 + 8 + 5 = 26，這是最終輸出。(原文計算錯誤，應為26)
下面程式中使用的方法如下：
宣告一個整數陣列和一個臨時變數 x 為 -1，然後將 `arr[0]` 設定為 `arr[0] * x`。
計算陣列的大小。宣告一個字首陣列 `prefix_arry[size]`。呼叫函式 `create_prefix_arr(arr, size, prefix_array)` 從給定陣列生成字首陣列。列印字首陣列。
呼叫函式 `maximize_sum(prefix_array, size)`，該函式將儲存陣列的最大和。
在函式 `void create_prefix_arr(int arr[], int size, int prefix_array[])` 內部：
將 `prefix_array[0]` 設定為 `arr[0]`。
從 `i = 0` 開始迴圈到陣列大小。在迴圈內，將 `prefix_array[i]` 設定為 `prefix_array[i-1] + arr[i]`。
在函式 `int maximize_sum(int prefix_array[], int size)` 內部：
宣告一個臨時變數 `temp` 並將其設定為 -1。
從 `i = 0` 開始迴圈到陣列大小。在迴圈內，將 `temp` 設定為 `max(temp, prefix_array[i])`。
宣告一個數組 `arr[temp + 1]` 並將其所有元素初始化為 0。
從 `i = 0` 開始迴圈到陣列大小。在迴圈內，設定 `arr[prefix_array[i]]++`。
宣告一個臨時變數 `max_sum` 並將其設定為 0。宣告一個變數 `int i = temp`。
開始 `WHILE i > 0` 迴圈。檢查 `IF arr[i] > 0`，則將 `max_sum` 設定為 `max_sum + i` 並遞減 `arr[i-1]--` 和 `arr[i]--`。否則，將 `i` 遞減 1。
返回 `max_sum`。
示例
#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
//create the prefix array
void create_prefix_arr(int arr[], int size, int prefix_array[]) {
prefix_array[0] = arr[0];
for(int i=0; i<size; i++) {
prefix_array[i] = prefix_array[i-1] + arr[i];
}
}
//find the maximum sum of prefix array
int maximize_sum(int prefix_array[], int size) {
int temp = -1;
for(int i = 0; i < size; i++) {
temp = max(temp, prefix_array[i]);
}
int arr[temp + 1];
memset(arr, 0, sizeof(arr));
for(int i = 0; i < size; i++) {
arr[prefix_array[i]]++;
}
int max_sum = 0;
int i = temp;
while(i>0) {
if(arr[i] > 0) {
max_sum = max_sum + i;
arr[i-1]--;
arr[i]--;
} else {
i--;
}
}
return max_sum;
}
int main() {
int arr[] = {2, 4, 1, 5, 2};
int x = -1;
arr[0] = arr[0] * x;
int size = sizeof(arr) / sizeof(arr[0]);
int prefix_array[size];
//call function to create a prefix array
create_prefix_arr(arr, size, prefix_array);
//print the prefix array
cout<<"Prefix array is: ";
for(int i = 0; i < size; i++) {
cout << prefix_array[i] << " ";
}
//print the maximum sum of prefix array
cout<<"\nMaximize the sum of array by multiplying prefix of array with -1 are:" <<maximize_sum(prefix_array, size);
return 0;
}輸出
如果執行上述程式碼，它將生成以下輸出
Prefix array is: -2 2 3 8 10 Maximize the sum of array by multiplying prefix of array with -1 are: 21
231 次瀏覽
