Login


F. Max Happiness(HARD)
Time limit per test: 2 second
Memory limit per test: 64 megabytes

Bugungi bayram tufayli Yoshlar ittifoqi hammaga sovg`a tarqatdi lekin bazilarga bu sovg`alar yoqmadi shu bois ularning kayfiyatlari manfiyga o`zgarib ketdi aksincha sovg`a yoqganlarniki esa o`ta ko`tarilib ketdi. Endi Sanjar o`ylab qoldi agar barcha talabalar kayfiyatlari qiymatini bir jadvalga joylashtirsak unda shunday qism jadval bor bu shu jadval summasi eng maksimal qilish kerak lekin u jadval bilan ishlash va Dinamik dasturlashda uncha kuchli emas unga yordam bering!

Input:
Birinchi qatorda N(0 < N < 107) va keyingi qatorda N ta talabalarning kayfiyatlari ai ( |ai| < 109)kiritiladi.

Output:
Eng maksimal qiymatga ega qism jadval summasini chop eting!

Input Output
3
1 2 3
3
1 -2 3
7
1 -2 3 -10 1 2 3
6
3
6
                 Submit code

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.