C++ 中求子数组最大和，且起始值和结束值相同
c++server side programmingprogramming
在本教程中，我们将讨论一个程序，用于求出子数组最大和，且起始值和结束值相同。
为此，我们将提供一个包含整数的数组。我们的任务是找到一个子数组，其两端元素相等，且和最大。
示例
#include <bits/stdc++.h>
using namespace std;
//求最大和
int maxValue(int a[], int n) {
unordered_map<int, int> first, last;
int pr[n];
pr[0] = a[0];
for (int i = 1; i < n; i++) {
pr[i] = pr[i - 1] + a[i];
if (first[a[i]] == 0)
first[a[i]] = i;
last[a[i]] = i;
}
int ans = 0;
for (int i = 0; i < n; i++) {
int start = first[a[i]];
int end = last[a[i]];
ans = max(ans, pr[end] - pr[start - 1]);
}
return ans;
}
int main() {
int arr[] = { 1, 3, 5, 2, 4, 18, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxValue(arr, n);
return 0;
}
输出
37
