資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學C++ 陣列中最大均衡和
問題陳述
給定一個數組 arr[]。找出 arr[] 中索引 i 的最大字首和值，該值也是字尾和值。
示例
如果輸入陣列為 −
Arr[] = {1, 2, 3, 5, 3, 2, 1}，則輸出為 11，因為 −
- 字首和 = arr[0..3] = 1 + 2 + 3 + 5 = 11；且
- 字尾和 = arr[3..6] = 5 + 3 + 2 + 1 = 11
演算法
- 遍歷該陣列，併為該陣列中的每個索引儲存字首和到 presum[] 中，其中 presum[i] 儲存子陣列 arr[0..i] 的和。
- 再次遍歷該陣列，並存儲另一個數組 suffsum[] 中的字尾和，其中 suffsum[i] 儲存子陣列 arr[i..n-1] 的和。
- 對每個索引檢查 presum[i] 是否等於 suffsum[i]，如果相等，則比較它們與迄今為止的最大值，
示例
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
int preSum[n];
int suffSum[n];
int result = INT_MIN;
preSum[0] = arr[0];
for (int i = 1; i < n; ++i) {
preSum[i] = preSum[i - 1] + arr[i];
}
suffSum[n - 1] = arr[n - 1];
if (preSum[n - 1] == suffSum[n - 1]) {
result = max(result, preSum[n - 1]);
}
for (int i = n - 2; i >= 0; --i) {
suffSum[i] = suffSum[i + 1] + arr[i];
if (suffSum[i] == preSum[i]) {
result = max(result, preSum[i]);
}
}
return result;
}
int main() {
int arr[] = {1, 2, 3, 5, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max equlibrium sum = " << getMaxSum(arr, n) << endl;
return 0;
}輸出
編譯並執行上述程式後，將生成以下輸出 −
Max equlibrium sum = 11
更新於： 10-Jan-2020
370 次瀏覽
廣告