数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：起始值和结束值相同的最大子数组和
在这个问题中，我们得到一个大小为n的数组arr[]，其中包含正值。我们的任务是编写一个程序，查找起始值和结束值相同的最大子数组和。
问题描述 − 在这里，我们需要找到一个子数组，使得索引i（子数组的起始索引）和j（子数组的结束索引）处的元素相同，即arr[i] = arr[j]。并且子数组元素的和最大化。
让我们来看一个例子来理解这个问题：
输入
arr[] = {2, 1, 3, 5, 6, 2, 4, 3}输出
23
解释
All subarrays which are starting and ending with the same element are:
{2, 1, 3, 5, 6, 2} = 2 + 1 + 3 + 5 + 6 + 2 = 19
{3, 5, 6, 2, 4, 3} = 3 + 5 + 6 + 2 + 4 + 3 = 23解决方案
为了解决这个问题，我们需要考虑这样一个事实：对于正值，子数组的和随着我们考虑的子数组大小的增加而增加。为此，我们将通过查找数组中数字的最左和最右出现来找到最大大小的子数组。如果它大于maxSum，则返回它们的和。
示例
程序说明了我们解决方案的工作原理：
#include <bits/stdc++.h>
using namespace std;
int maxValue(int arr[], int n) {
unordered_map<int, int> startIndex, endIndex;
int sumArr[n];
sumArr[0] = arr[0];
for (int i = 1; i < n; i++) {
sumArr[i] = sumArr[i − 1] + arr[i];
if (startIndex[arr[i]] == 0)
startIndex[arr[i]] = i;
endIndex[arr[i]] = i;
}
int maxSum = 0;
for (int i = 0; i < n; i++) {
int left = startIndex[arr[i]];
int right = endIndex[arr[i]];
maxSum = max(maxSum, sumArr[right] − sumArr[left − 1]);
}
return maxSum;
}
int main() {
int arr[] = { 2, 1, 3, 5, 6, 2, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum subarray such that start and end values are same is "<<maxValue(arr, n);
return 0;
}输出
The maximum sum subarray such that start and end values are same is 23
更新于：2020年12月9日
471 次浏览
广告