Official Analysis

Explanation

The given equation demonstrates how as the distance between the left and right boundaries increase, the value of the equation decreases. Thus, in order to maximize the value, it is best to set two of the most beautiful sights at the boundaries. Then, the distance between the boundaries is decreased, meaning the value of the equation is increased. Knowing this, we can create a new equation reflecting that two of the sights are at the boundaries.

This simplifies the problem into finding a middle sight and adding it to the maximum $b_l + l$ from the left and the maximum $b_r + r$ from the right.

In order to do so, we can compute a prefix array that stores the maximum value of $\texttt{beauty}[i] + i$ for sights to the left of each point, and a suffix array that stores the maximum value of $\texttt{beauty}[i] - i$ for sights to the right of each point.

For each possible middle sight, we combine the best contributions from its left and right with its own beauty to maximize the result.

Implementation

Time Complexity: $\mathcal{O}(n)$

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

int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		cin >> n;
		vector<int> beauty(n);

Copy
import java.io.*;
import java.util.*;

public class RunningMiles {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int testNum = io.nextInt();
		for (int t = 0; t < testNum; t++) {
			int n = io.nextInt();
			int[] beauty = new int[n];

Copy
for _ in range(int(input())):
	n = int(input())
	beauty = list(map(int, input().split()))
	pref = [0] * n
	suff = [0] * n

	for i in range(n):
		pref[i] = beauty[i] + i
		suff[i] = beauty[i] - i