Skip to Content
CTRL K

Running Miles

Análisis oficial 

Explicación

La ecuación dada muestra cómo, a medida que aumenta la distancia entre los extremos izquierdo y derecho, el valor de la ecuación disminuye. Así, para maximizar el valor, es mejor colocar dos de las vistas más hermosas en los extremos. Entonces, la distancia entre los extremos disminuye, lo que significa que el valor de la ecuación aumenta. Sabiendo esto, podemos crear una nueva ecuación que refleje que dos de las vistas están en los extremos.

bi1+bl+br+(l−r)=bi1+(bl+l)+(br−r). b_{i_1} + b_{l} + b_{r} + (l - r) = b_{i_1} + (b_{l} + l) + (b_{r} - r).

Esto simplifica el problema a hallar una vista del medio y sumarla al máximo bl+lb_l + l de la izquierda y al máximo br+rb_r + r de la derecha.

Para hacerlo, podemos calcular un arreglo de prefijos que guarda el valor máximo de beauty[i]+i\texttt{beauty}[i] + i para las vistas a la izquierda de cada punto, y un arreglo de sufijos que guarda el valor máximo de beauty[i]−i\texttt{beauty}[i] - i para las vistas a la derecha de cada punto.

Para cada vista del medio posible, combinamos las mejores contribuciones de su izquierda y derecha con su propia belleza para maximizar el resultado.

Implementación

Complejidad temporal: O(n)\mathcal{O}(n)

#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);
		for (int i = 0; i < n; i++) { cin >> beauty[i]; }
 
		vector<int> pref_max(n);
		vector<int> suff_max(n);
		for (int i = 0; i < n; i++) {
			pref_max[i] = beauty[i] + i;
			suff_max[i] = beauty[i] - i;
		}
 
		for (int i = 1; i < n; i++) { pref_max[i] = max(pref_max[i], pref_max[i - 1]); }
		for (int i = n - 2; i >= 0; i--) {
			suff_max[i] = max(suff_max[i], suff_max[i + 1]);
		}
 
		int ans = 0;
		for (int i = 1; i < n - 1; i++) {
			ans = max(ans, pref_max[i - 1] + beauty[i] + suff_max[i + 1]);
		}
 
		cout << ans << '\n';
	}
}
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];
			for (int i = 0; i < n; i++) { beauty[i] = io.nextInt(); }
 
			int[] pref_max = new int[n];
			int[] suff_max = new int[n];
 
			for (int i = 0; i < n; i++) {
				pref_max[i] = beauty[i] + i;
				suff_max[i] = beauty[i] - i;
			}
 
			for (int i = 1; i < n; i++) {
				pref_max[i] = Math.max(pref_max[i], pref_max[i - 1]);
			}
			for (int i = n - 2; i >= 0; i--) {
				suff_max[i] = Math.max(suff_max[i], suff_max[i + 1]);
			}
 
			int ans = 0;
			for (int i = 1; i < n - 1; i++) {
				ans = Math.max(ans, pref_max[i - 1] + beauty[i] + suff_max[i + 1]);
			}
			io.println(ans);
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}
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
 
	for i in range(1, n):
		pref[i] = max(pref[i], pref[i - 1])
	for i in range(n - 2, -1, -1):
		suff[i] = max(suff[i], suff[i + 1])
 
	ans = 0
	for i in range(1, n - 1):
		ans = max(ans, pref[i - 1] + suff[i + 1] + beauty[i])
 
	print(ans)
Fundamentos