Perle2

Se observă că găsirea unei subsecvenţe [i,j] care maximizează valoarea (A[i]+A[i+1]+...+A[j]) - K*(j-i+1) este echivalentă cu găsirea unei subsecvenţe care maximizează valoarea A[i]-K+A[i+1]-K+...+A[j]-K. Această observaţie duce la ideea de a scădea K din fiecare element al vectorului iniţial şi de a căuta apoi subsecvenţa de sumă maximă. Subsecvenţa de sumă maximă (mai multe detalii aici) poate fi localizată în complexitate timp O(N), iar o soluţie ce ar fi implementat această idee ar fi obţinut 100 de puncte.