Dessert Wizard

All submissions for this problem are available.
It's finally summer in Chefland! So our chef is looking forward to prepare some of the best "beattheheat" dishes to attract more customers. He summons the Wizard of Dessert to help him with one such dish.
The wizard provides the chef with a sequence of N ingredients where the i^{th} ingredient has a delish value of D[i]. The preparation of the dish takes place in two phases.
Phase 1 : The chef chooses two indices i and j and adds the ingredients i, i+1, ..., j to his dish. He also finds the sum of the delish value in this range i.e D[i] + D[i+1] + ... + D[j].
Phase 2 : The chef chooses two more indices k and l and adds the ingredients k, k+1, ..., l to his dish. He also finds the sum of the delish value in this range i.e D[k] + D[k+1] + ... + D[l].
Note that 1 ≤ i ≤ j < k ≤ l ≤ N.
The total delish value of the dish is determined by the absolute difference between the values obtained in the two phases. Obviously, the chef wants to maximize the total delish value for his dish. So, he hires you to help him.
Input
First line of input contains an integer T denoting the number of test cases. For each test case, the first line contains an integer N denoting the number of ingredients. The next line contains N space separated integers where the i^{th} integer represents the delish value D[i] of the i^{th} ingredient.
Output
Print the maximum delish value of the dish that the chef can get.
Constraints
 1 ≤ T ≤ 50
 2 ≤ N ≤ 10000
 1000000000 (−10^{9}) ≤ D[i] ≤ 1000000000 (10^{9})
Example
Input: 2 5 1 2 3 4 5 4 1 1 1 1 Output: 13 4
Explanation
Example case 1.
Chef can choose i = j = 1, k = 2, l = 5.
The delish value hence obtained is  (2+3+4+5) − (1)  = 13 .
Example case 2.
Chef can choose i = 1, j = 2, k = 3, l = 4.
The delish value hence obtained is  ( ( −1 ) + ( −1 ) ) − ( 1 + 1 )  = 4 .
Author:  viv001 
Tester:  tuananh93 
Editorial  http://discuss.codechef.com/problems/DELISH 
Tags  dynamicprog june13 simple viv001 
Date Added:  30032013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
@abigale:no it's n't
gettin ...TLE ..optimization
Tipically, no help can be
@Admin plz check my
suppose that for phase 1 the
@avastpulkit its given k is
@aditya11_iiitm .. ohh
can i,j and k,l take same
can i,j and k,l take same
do the d[i] take only integer
@kenpachi, Please read
@kuruma thks
can any one provide some test
damn... that's why i like
Help me someone... TLE. WA.
what complexity algorithm is
a silly mistake and it take
do u we have to use some
@firebolt_r13: I think it can
@himank77 ok, got my problem,
can anyone give some corner
See for the first test case
@h43k3r See the constraint 1
will it get cleared by o(n^2)
@Admin  can you please
What do to when n is less
Why o(n^2) is getting TLE ,
guys who r getting WA in C,
Can the Chef add the same
does it require any special
@m_garg : O(N^2) would give
@ankit2038 : you assume that
SO what could be the order of
Can someone give me some
Geting run time error :(
can someone please give some
How does one get the runtime
@admin Why the solutions were
RTE WA WA WA.... :(
can some 1 give me more test
My code gives all the right
WA WA WA :(
@hitmank77, am gettin 11 but
@himank77 i m getting 11 for
I've done some tests,
@all, I'm also struggling
always i have to use all the
Tested correctly for all test
@all ... although this sounds
3 WA, 10 TLE and at last AC
@manish712 is there any
I am getting correct ans for
@joamon What's wrong in using
I got AC in my first attempt.
any specific type of algo
nice problem, 2 days for me
Just wasted my 2 Days because
@Admin plz check my
getting WA, working fine with
I am getting time limit
Getting WA. Don't know if the
finally got AC :) it took
same problem like
i thnk mst f them are
nested loops causing lot of
Do the two pair of indices
i am getting a WA when using
my algorithm runs in linear
@ admin ":
oh my god.....asssigned i
Phew, AC after 8 attempts! :)
its giving wrong answer here
Please give some more test
tried all test cases that i
tle.....have to refine more
Codechef trolled........@
@admin  what is the
@admin id : 2243653 help
hey any body getting RUNTIME
@suzal.. yep.. same error...
Whoo! Finally AC after 5
admin@ please provide corner
Finaly, a green tick!
m getting runtime error??? :(
@admin, corner case where I'm
1 5 2 2 should give 9 , am
Indeed, 9 is the answer.
@riaz2012  no it will give
@KHANZAId09...hav u got a
The answer is 9, 4  5 = 9
Is there something wrong
900 people solved this... I
@kunalbansal16: sorry, it
just figuring out the test
@redherring no 21 would be
@redherring @kunalbansal16
For example my code doesn't
why abs function in C giving
finally Got AC after 33 WA :P
Why are ADMINS not deleting
Finally AC after 10 straight
@raman92, I believe that in
my code is correct. I don't
I have tried this inputs: 5 3
i tried all these cases ,its
can someone give me corner
actually you dont need to
you dont need to worry about
Let j....i be the indices ,
Can't blve man.. I got 2nd
@sumanth232 I used the same