Maximum sum subarray such that start and end values are same in C++
-
10-09-2020 - |
Вопрос
In this tutorial, we will be discussing a program to find maximum sum subarray such that start and end values are same.
For this we will be provided with an array containing integers. Our task is to find the subarray with the maximum sum such that the elements are both its ends are equal.
Example
#include <bits/stdc++.h> using namespace std; //finding the maximum sum 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; }
Output
37
Не связан с Tutorialspoint