資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告