Problem Statement

You are given an array a[1..N] of integers and an integer K, you may negate at most K contiguous subarrays. Each operation flips the sign of every element in the chosen subarray; overlapping flips are allowed and stack . Find the maximum resulting array sum . Input Format The first line contains a integer, n, denoting the size of the array. The second line contains a integer, k, denoting the constraint k. Each line i of the n subsequent lines (where 0 ≤ i < n) contains a integer, a[i]. Constraints 1 ≤ n ≤ 10 5 1 ≤ k ≤ 10 5 -10 9 ≤ a[i] ≤ 10 9 Sample Test Cases Case 1 Input: 5 2 -10 20 -30 40 -50 Output: 130 Explanation: n=5, k=2, a=[-10, 20, -30, 40, -50] With 2 flip operations, negate just a[2]=-30 (1 op) and a[4]=-50 (1 op): Result = [-10, 20, 30, 40, 50] -> sum = 130 Case 2 Input: 3 1 10 20 30 Output: 60 Explanation: n=3, k=1, a=[10, 20, 30] All elements are already positive. Any flip would only reduce the sum. Answer = 60 (no flips used). Case 3 Input: 4