이 튜토리얼에서는 시작 값과 끝 값이 같도록 최대 합 하위 배열을 찾는 프로그램에 대해 설명합니다.
이를 위해 정수를 포함하는 배열이 제공됩니다. 우리의 임무는 요소가 양쪽 끝이 같도록 최대 합을 가진 하위 배열을 찾는 것입니다.
예시
#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