Maximise Adjacent Sum - Starters 123

using namespace std;

int main() {
int t;
cin >> t;
while (t–) {
int n;
cin >> n;

``````    vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}

sort(arr.begin(), arr.end()); // Sort in descending order

long long result = 0;
for (int i = 1; i < n; i++) {
result += (arr[i] + arr[i - 1]);
}

cout << result << endl;
}

return 0;
``````

}

Why are adding the maximum element only once? Only the first two elements of the sorted array should be included once so that the sum is maximized. Other elements should be included twice.

1 Like

Because you are only summing them up based on f(A).

The problem is not asking you to sum the sorted elements. It’s asking you to find an arearrangement of elements in A, so the sum based on f(A) is the maximum possible.

Hint 1:
You can rearrange the array to the order of elements you want

Hint 2:
If instead of numbers, you take the sum as A = [a1, a2, a3, a4], how does it look like the sum?
(a1 + a2) + (a2 + a3) …

Do algebra, and find patterns