Avoid boredom
Practice
3.6 (129 votes)
Recursion
Dynamic programming
Approved
Easy Medium
Problem
7% Success 3796 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Exams are approaching soon and everyone tries to get ready for them. So, Omar decides to begin studying his subjects. He has N subjects and he wants to study M of them today. According to Omar, every subject has an interest level, \(A_i\) which indicates how much Omar likes that subject. Unfortunately, Omar feels bored easily, so he decides to choose a collection of interesting and boring subjects. Actually, Omar wants to choose M subjects such that the summation S of the absolute difference between every two adjacent subjects' interest levels is maximum as possible. Omar will put the selected M subjects in a group in the same order as described in the input, and then he will proceed to calculate S.

Please help Omar and rescue him from boredom

Input:

First line of the input contains an integer T denoting the number of test cases.
First line of every test-case contains two space separated integers N and M.
Second line of every test case contains N space separated integers \(A_i\) denoting the interest level for \(i^{th}\) subject.

*Output: *

For each case, print the above described S in a separate line.

Constraints:

  • \(1 \le N \le 100\).
  • \(1 \le M \le N\).
  • \(1 \le A_i \le 10^{9}\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
3 votes
Tags:
Ad-HocData StructuresOpenApprovedEasyMathamatics
Points:30
173 votes
Tags:
Binary search algorithmHiringRecursionBrute-force searchEasy-MediumReadyApprovedBacktracking
Points:20
38 votes
Tags:
ApprovedBinary SearchData StructuresEasyHash MapsHashing AlgorithmOpenSorting