[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

# cook your dish here
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
{
// your code goes here
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;
}
// your code goes here
return 0;
}


Also read : Black cells in a chessboard solution codechef

Also read : Large Square solution codechef

Also read : Bus full of passengers solution codechef

Also read : Friend Groups In A Line solution codechef 

[Solved] Maximise the Subsequence Sum codechef solution


Also read :  Polycarp and String Transformation solution codeforces

No Comments, Be The First!

Your email address will not be published.