C++ में समान शुरुआत और अंत मान वाले उपसरणी का अधिकतम योग

एक पूर्णांक सरणी दी गई है। ऐसा उपसरणी ढूंढें जिसका योग अधिकतम हो और जिसके पहले और अंतिम तत्व समान हों।

उदाहरण: {1, 3, 5, 2, 4, 18, 2, 3} → अधिकतम योग 37 (उपसरणी 3 से 3 तक)।

समाधान दृष्टिकोण

1. प्रत्येक मान की पहली और अंतिम घटना के इंडेक्स संग्रहीत करें (हैश मैप)।
2. प्रीफिक्स योग सरणी pr बनाएं।
3. प्रत्येक इंडेक्स i के लिए, मान a[i] की पहली (start) और अंतिम (end) घटना लें।
4. उपसरणी योग = pr[end] - pr[start-1]।
5. अधिकतम योग वापस करें।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

int maxValue(int a[], int n) {
    unordered_map 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] - (start > 0 ? pr[start - 1] : 0));
    }
    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