Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

# Max Prefix

Easy
0/40
Average time to solve is 7m
Contributed by

## Problem statement

You are given an array 'A' of length 'N'. You can perform the operation defined below any number of times (Possibly 0).

``````Choose 'l', 'r' (1 <= 'l' <= 'r' <='N') and reverse the subarray from 'l' to 'r'.
``````

After that, Return the maximum possible sum of the prefix of this array of length 'K'.

For Example:-
``````Let 'N' = 5, 'K' = 3, 'A' = [4, 2, 1, 2, 2].
We can reverse the subarray from index 3 to 4 (1-based indexing).
Array becomes [4, 2, 2, 1, 2].
Our answer is 8.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:-
``````1 <= 'T' <= 10
1 <= 'K' <= 'N' <= 10^5
1 <= 'A[i]' <= 10^3

The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec
``````
##### Sample Input 1:-
``````2
2 2
1 3
3 2
2 2 3
``````
##### Sample Output 1:-
``````4
5
``````
##### Explanation of sample input 1:-
``````First test case:-
We do not need to reverse any subarray.
Our answer is 4.

Second test case:-
We can reverse the subarray from index 1 to 3 (1-based indexing).
Array becomes [3, 2, 2].
Our answer is 5.
``````
##### Sample Input 2:-
``````2
4 3
4 3 2 1
5 5
1 2 3 4 5
``````
##### Sample Output 2:-
``````9
15
``````
Console