Programozás‎ > ‎Feladatok‎ > ‎

Maximális összegű résztömb

Adott az N-elemű A={a1,a2,…,aN} tömb. Keressük a a legnagyobb összegű 

  • szomszédos elemekből
  • tetszőleges elemekből
álló résztömbjét. Az üres halmaz nem számít megoldásnak


Feladat

Számítsuk ki a maximális összegeket mindkét esetben.

Bemenet

A bemenet első sora tesztesetek T számát adja meg (1 <= T <= 10). Minden teszteset két sorból áll.
Az elsőben N értéke van (1 <= N <=100000), a másodikban N darab egész szám (-10000 <= ai <= 10000).

Kimenet

Minden tesztesethez egy sor tartozik, benne két szóközzel elválasztott egész, az első és második feladat megoldása (a maximális összeg értéke). Legalább egy elemet ki kell választani a tömbből.

Példa

Bemenet  Kimenet
2
4
1 2 3 4
6
2 -1 2 3 4 -5 
10 10
10 11


Tesztadatok

Címkék

Algoritmusok: dinamikus programozás

megoldás