Maximum Subarray II

Problema

Se nos pide hallar el subarreglo máximo con tamaño en $[a,b]$ .

Pista 1

Podemos observar que realizaremos consultas de suma de rango para nuestro subarreglo.

Por lo tanto, deberíamos construir un arreglo de sumas de prefijos para realizar estas consultas.

Solución

Explicación

Observemos que estamos intentando maximizar $\textrm{pfx}[i] - \textrm{pfx}[j]$ . Como $j$ está garantizado de estar dentro de la ventana $[i-b,i-a]$ , podemos construir una ventana deslizante de tamaño $b-a+1$ , y computar $\max_{A\le i \le B}(\textrm{pfx}[i]-\textrm{pfx}[j])$ .

C++

Implementación usando un multiconjunto en C++:


#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
const ll LINF = 1e18;
 
int N, A, B;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> A >> B;  // lectura de variables
 
	vector<long long> pfx(N + 1);
	for (int i = 1; i <= N; i++) {
		int a;
		cin >> a;
		pfx[i] = a + pfx[i - 1];  // construcción de nuestra suma de prefijos
	}
 
	ll ret = -LINF;
	multiset<ll> ms;
 
	// podemos mantener una ventana deslizante de tamaño B - A + 1,
	// y luego hallar el menor pfx[j] usando multiset
	for (int i = A; i <= N; ++i) {
		if (i > B) ms.erase(ms.find(pfx[i - B - 1]));  // borrar el elemento si el tamaño > B
		ms.insert(pfx[i - A]);
		ret = max(ret,
		          pfx[i] - *ms.begin());  // queremos minimizar ms.begin() aka pfx[j]
	}
 
	cout << ret << "\n";
}