ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อค้นหาอาร์เรย์ย่อยผลรวมสูงสุด โดยที่ค่าเริ่มต้นและสิ้นสุดจะเท่ากัน
สำหรับสิ่งนี้เราจะได้รับอาร์เรย์ที่มีจำนวนเต็ม หน้าที่ของเราคือค้นหาอาร์เรย์ย่อยที่มีผลรวมสูงสุดเพื่อให้องค์ประกอบทั้งสองปลายเท่ากัน
ตัวอย่าง
#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;
} ผลลัพธ์
37
