Dãy con liên tiếp tổng lớn nhất với đầu và cuối bằng nhau trong C++

Mô tả bài toán

Cho mảng arr[] toàn số dương. Tìm dãy con liên tiếp có tổng lớn nhất sao cho phần tử đầu và cuối của dãy con bằng nhau.

Ví dụ: arr = {2,1,3,5,6,2,4,3} → 23 (dãy con [3,5,6,2,4,3] từ chỉ số 2 đến 7).

Giải thuật

1. Tính mảng tiền tố sumArr.
2. Duyệt mảng, lưu chỉ số xuất hiện đầu tiên (startIndex) và cuối cùng (endIndex) của mỗi giá trị.
3. Với mỗi i, lấy left = startIndex[arr[i]], right = endIndex[arr[i]], tổng = sumArr[right] - sumArr[left-1]. Cập nhật maxSum.

Ví dụ minh họa (C++)

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

int maxValue(int arr[], int n) {
    unordered_map startIndex, endIndex;
    vector sumArr(n);
    sumArr[0] = arr[0];
    for (int i = 1; i < n; i++) {
        sumArr[i] = sumArr[i-1] + arr[i];
        if (!startIndex.count(arr[i])) 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] - (left? sumArr[left-1] : 0));
    }
    return maxSum;
}

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

Đầu ra

Maximum sum: 23