I managed to find a recursive solution which gives tle for last test case of second subtask and first test case of last. This is because I couldn't find a way to cache the computed value so there was repitition of calculation.
My process included finding all possible negatives in pairs and then taking triplets to find all cases that produce negative sum . I take the negatives only in a seperate array and all I now have to do is find all combinations in which no two negatives are adjacent .
Here is the link to my solution(20pts) : www.codechef.com/viewsolution/18569209
I do understand all I have to do is store the best possible sum from index i to n-1 for every index i and also the array traversal which has to be stored in a 2d array for every i in every row. I do not understand how to do it. Please help.