ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n ซึ่งประกอบด้วยค่าบวก งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของ subarray สูงสุดซึ่งค่าเริ่มต้นและสิ้นสุดจะเท่ากัน
คำอธิบายปัญหา − ที่นี่ เราจำเป็นต้องค้นหาอาร์เรย์ย่อยที่องค์ประกอบที่ดัชนี i (ดัชนีเริ่มต้นของ subarray) และ j (ดัชนีสิ้นสุดของ subarray) เหมือนกัน เช่น arr[i] =arr[j] และผลรวมขององค์ประกอบของอาร์เรย์ย่อยจะถูกขยายให้ใหญ่สุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {2, 1, 3, 5, 6, 2, 4, 3} ผลลัพธ์
23
คำอธิบาย
All subarrays which are starting and ending with the same element are:
{2, 1, 3, 5, 6, 2} = 2 + 1 + 3 + 5 + 6 + 2 = 19
{3, 5, 6, 2, 4, 3} = 3 + 5 + 6 + 2 + 4 + 3 = 23 แนวทางการแก้ปัญหา
ในการแก้ปัญหา เราต้องพิจารณาข้อเท็จจริงที่ว่าสำหรับค่าบวก ผลรวมของอาร์เรย์ย่อยจะเพิ่มขึ้นตามขนาดของอาร์เรย์ย่อยที่เราพิจารณา สำหรับสิ่งนี้ เราจะพบอาร์เรย์ย่อยที่มีขนาดสูงสุดโดยการค้นหาตัวเลขที่เกิดขึ้นทางซ้ายสุดและขวาสุดในอาร์เรย์ และส่งคืนผลรวมหากมากกว่าค่า maxSum
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
int maxValue(int arr[], int n) {
unordered_map<int, int> startIndex, endIndex;
int sumArr[n];
sumArr[0] = arr[0];
for (int i = 1; i < n; i++) {
sumArr[i] = sumArr[i − 1] + arr[i];
if (startIndex[arr[i]] == 0)
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] − sumArr[left − 1]);
}
return maxSum;
}
int main() {
int arr[] = { 2, 1, 3, 5, 6, 2, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum subarray such that start and end values are same is "<<maxValue(arr, n);
return 0;
} ผลลัพธ์
The maximum sum subarray such that start and end values are same is 23
