# [Solved] Maximise the Subsequence Sum codechef solution

## Maximise the Subsequence Sum codechef solution

Chef has an array AA containing NN integers. The integers of the array can be positive, negative, or even zero.

Chef allows you to choose at most KK elements of the array and multiply them by 1−1.

Find the maximum sum of a subsequence you can obtain if you choose the elements of the subsequence optimally.

Note: A sequence aa is a subsequence of a sequence bb if aa can be obtained from bb by deletion of several (possibly, zero or all) elements. For example, [3,1][3,1] is a subsequence of [3,2,1][3,2,1] and [4,3,1][4,3,1], but not a subsequence of [1,3,3,7][1,3,3,7] and [3,10,4][3,10,4]. Note that empty sequence is also a subsequence.

### Input Format

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains two space-separated integers N,KN,K.
• The second line of each test case contains NN space-separated integers A1,A2,...,ANA1,A2,…,AN

### Output Format

For each test case, print a single line containing one integer – the maximum sum of a subsequence you can obtain.

### Constraints

• 1T151≤T≤15
• 1N1051≤N≤105
• 0KN0≤K≤N
• 104Ai104−104≤Ai≤104
• Sum of NN over all test cases does not exceed 106106

### Sample Input 1

3
6 2
6 -10 -1 0 -4 2
5 0
-1 -1 -1 -1 -1
3 3
1 2 3


### Sample Output 1

22
0
6


### Explanation

Test case 11: It is optimal to multiply 10,4−10,−4 with 1−1 and then take the subsequence [6,10,4,2][6,10,4,2].

Test case 22: It is optimal to choose empty subsequence with a sum equal to 00.

Test case 33: We can take subsequence [1,2,3][1,2,3]. Here, we do not multiply 1−1 with any element.

# Solution

## Python

try:
for _ in range(int(input())):
n, k = map(int, input().split())
N = list(map(int, input().split()))
N.sort()

sub_seq_sum = 0

for value in N:
if value >= 0:
sub_seq_sum += value

for idx in range(k):
if N[idx] < 0:
sub_seq_sum -= N[idx]

print(sub_seq_sum)

except EOFError as e:
pass

## Java

/* package codechef; // don’t place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner scan=new Scanner(System.in);
int T=scan.nextInt();
for(int i=0;i<T;i++){
int n=scan.nextInt();
int k=scan.nextInt();
int[] arr=new int[n];
for(int j=0;j<arr.length;j++){
arr[j]=scan.nextInt();
}
Arrays.sort(arr);
for(int j=0;j<k;j++){
if(arr[j]<0){
arr[j]=arr[j]*-1;
}
}
int sum=0;
for(int j=0;j<arr.length;j++){
if(arr[j]>0){
sum+=arr[j];
}
}
System.out.println(sum);
}
scan.close();
}
}

## C++

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–){
int n,k,i;
cin>>n>>k;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(i=0;i<k;i++){
if(a[i]<0){
a[i]=a[i]*(-1);}
else
{
break;

}
}
long long int sum=0;

for(i=0;i<n;i++){
if (a[i]>0)
{
sum=sum+a[i];
}
}
cout<<sum<<endl;
}
return 0;
}

Also read : Large Square solution codechef

Also read : Bus full of passengers solution codechef

Also read : Friend Groups In A Line solution codechef    