SFLIP  Segment Flip
You are given N number a_{1}, a_{2}, ... , a_{N}. In a segment flip, you can pick a contiguous segment a_{i}, a_{i+1}, ... , a_{j} of these numbers, where i<=j and negate all the numbers in this segment.
You are permitted atmost K segment flip operations overall. Also, no 2 segments that you pick can overlap. That is, if you flip a_{i}, ... , a_{j} and a_{k}, ... , a_{l} then either j < k or l < i.
Your aim is to maximize the sum of all the numbers in the resulting sequence by applying appropriate segment flip operations meeting these constraints.
For instance, suppose the sequence is 5, 2, 3 and you are allowed a single segment flip. The best sum you can achieve is 6, by flipping all 3 numbers as a single segment to 5, 2, 3.
Input
The first line contains 2 integers N and K. The next line contains N integers, the initial values of a_{1}, a_{2}, ... , a_{N}.
Output
A single integer denoting the maximum possible sum of the final array.
Constraints
0 <= K <= N
10000 <= a_{i} <= 10000
1 <= N <= 100000
Example
Input: 3 1 5 2 3 Output: 6
hide comments
PetarV:
20120421 13:19:01
You probably didn't get WA 49. There are 50 tests and I think it is SPOJ's procedure to go through all the testdata, then return WA with the timestamp of the first testcase that failed. Given that your execution times are around 0.01s, I'd say that you got WA on one of the first test cases. 

Ivaylo Chernev:
20120419 10:36:16
How many test are there ?? I got WA 49 :O 
Added by:  jack(chakradarraju) 
Date:  20110810 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Proposed by venkateshb 