FastPrep
Problem · Dynamic Programming

The Best Subsequence || Find the minimum of special value of a subsequence

Learn this problem
● HardGE VernovaOA

Problem statement

You are given an array arr of size n and an integer k. A subsequence is defined as a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. You need to find a subsequence of size k and calculate its special value.

The special value of a subsequence of size k is defined as: Summation of absolute difference of consecutive numbers. For i = 2 to k, abs(pi - p(i-1)).

Your task is to find the minimum possible special value among all subsequences of size k in the array.

Function

findMinimumSpecialValue(arr: int[], k: int) → int

Examples

Example 1

arr = [9, 5, 1, 4, 9]k = 2return = 0
Subsequence : {9, 9}

Example 2

arr = [9, 5, 1, 4, 9, 100]k = 3return = 5
Subsequence : {9, 5, 4}

Constraints

🌷
drafts saved locally
public int findMinimumSpecialValue(int[] arr, int k) {
  // write your code here
}
arr[9, 5, 1, 4, 9]
k2
expected0
checking account