โปรแกรมหาผลรวม subarray สูงสุด ที่ค่าเริ่มต้นและสิ้นสุดเท่ากันใน C++

ให้อาร์เรย์ arr[] หา subarray ที่ arr[start]==arr[end] และผลรวมมากที่สุด

ตัวอย่าง: arr=[2,1,3,5,6,2,4,3] → 23 (subarray [3,5,6,2,4,3] เริ่ม 3 จบ 3)

วิธีแก้ปัญหา

เพราะค่าทุกตัวเป็นบวก → subarray ยิ่งยาวผลรวมยิ่งมาก หา first/last occurrence ของแต่ละค่า คำนวณผลรวมด้วย Prefix Sum เลือกมากสุด

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

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

int maxValue(int arr[], int n) {
    unordered_map first, last;
    vector pref(n);
    pref[0] = arr[0];
    for (int i = 1; i < n; i++) {
        pref[i] = pref[i-1] + arr[i];
        if (!first.count(arr[i])) first[arr[i]] = i;
        last[arr[i]] = i;
    }
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        int l = first[arr[i]], r = last[arr[i]];
        int sum = pref[r] - (l > 0 ? pref[l-1] : 0);
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

int main() {
    int arr[] = {2,1,3,5,6,2,4,3};
    int n = 8;
    cout << maxValue(arr, n); // 23
    return 0;
}

อินพุต

arr[] = {2, 1, 3, 5, 6, 2, 4, 3}

เอาต์พุต

23