Maximum sum subarray such that start and end values are same in C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมหาผลรวมสูงสุดของเซ็บอาร์เรย์ (subarray) ที่ค่าเริ่มต้นและค่าสิ้นสุดเท่ากัน

เราจะได้รับอาร์เรย์จำนวนเต็ม งานคือหาเซ็บอาร์เรย์ที่มีผลรวมสูงสุด โดยที่องค์ประกอบทั้งสองข้างมีค่าเท่ากัน

ตัวอย่างโค้ด

#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] - (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