Indicatii Skyline

Soluție oficială(Vintilă Valentin)
Folosind o stivă, vom calcula pentru fiecare ‘bloc’ alte două ‘blocuri’ care să fie, din punct de vedere al înălțimii, strict mai mici decât cel inițial. Unul din aceste blocuri va fi situat în stânga, iar celălalt în dreapta. Aceste rezultate vor fi reținute în vectorii S, respectiv D. Acest algoritm este foarte asemănător cu cel folosit la problema nrapp.

De asemenea, vom calcula un vector de sume parțiale sum care va reține în poziția i lățimea primelor i blocuri.

În urma calculării acestor vectori, pornim cu o arie maximă egală cu 0 și iterăm de la 1 până la n, actualizând, dacă este nevoie, valoarea maximă cu v[i] * (sum[D[i]-1] - sum[S[i]]).

Complexitatea finală: O(n) amortizat.