 New update is available. Click here to update.

# Max Prefix

Contributed by
Tushar Gupta
Last Updated: 23 Feb, 2023
Easy 0/40
Avg time to solve 7 mins
Success Rate 90 % Share 2 upvotes

## 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].
``````
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.

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