h1(#MaxSubSum). 'A. MaxSubSum':problema/MaxSubSum

Datorita limitei lui N (N <= 2.000), solutia triviala in care matricea este calculata iar apoi este aplicat algoritmul pentru submatrice de suma maxima O(N³) nu va intra in timp.

Datorita limitei lui N (N <= 2.000), solutia triviala in care matricea este calculata iar apoi este aplicat algoritmul pentru submatrice de suma maxima O(N^3) nu va intra in timp.

Se observa ca orice submatrice este de fapt data de o subsecventa din primul sir *S1* si o subsecventa din al doilea *S2*. Suma elementelor a submatricei este de fapt *len(S1) * sum(S2) + len(S2) * sum(S1)*.

Se va calcula pentru fiecare sir *max[i] = suma maxima a unei subsecvente de lungime i* in O(N²).
Avand *max1* si *max2* (pentru cele doua siruri), in O(N²) putem incerca toate lungimile *L1*, *L2* (1 <= L1 <= N, 1 <= L2 <= M) de secvente posibile pentru cele doua siruri iar cu formula de mai sus putem calcula suma maxima ce se poate obtine pentru lungimile respective. Vom salva si afisa valoarea maxima. Complexitatea finala este O(N²)

Se va calcula pentru fiecare sir *max[i] = suma maxima a unei subsecvente de lungime i* in O(N^2).
Avand *max1* si *max2* (pentru cele doua siruri), in O(N^2) putem incerca toate lungimile *L1*, *L2* (1 <= L1 <= N, 1 <= L2 <= M) de secvente posibile pentru cele doua siruri iar cu formula de mai sus putem calcula suma maxima ce se poate obtine pentru lungimile respective. Vom salva si afisa valoarea maxima.

h1(#MaxSubSum). 'B. Avioane2':problema/Avioane2