Subtask 1

Realize a DP state:

• ~DP_{i, j}~: the minimum sum of absolute differences for the ~i^\text{th}~ integer in the array with a subsequence of length ~j~.

Then, for each given state, consider choosing any integer in the array before the ~i^\text{th}~ one:

Thus, ~DP_{i, j} = \min(DP_{k, j-1} + |A_i - A_k|)~, where ~1 \le k < i~ and ~|A - B|~ represents the absolute difference between ~A~ and ~B~.

Time Complexity: ~\mathcal{O}(N^2K)~

Subtask 2

Realize that the transition can be optimized with ~2K~ Fenwick trees or ~2K~ segment trees:

• Maintain ~K~ for all integers that come before ~i~ but have ~A_k \le A_i~ with ~\min(DP_{k, j-1} - A_k)~ at the ~A_k^\text{th}~ index.
• Maintain ~K~ for all integers that come before ~i~ but have ~A_k > A_i~ with ~\min(DP_{k, j-1} + A_k)~ at the ~A_k^\text{th}~ index.

Then, for each given state, ~DP_{i, j} = \min(\text{query_smaller}(A_i) + A_i), \text{query_bigger}(A_i) - A_i)~, where ~\text{query_smaller}(IDX)~ returns the minimum ~\min(DP_{k, j-1} - A_k)~ for all indices less than or equal to ~IDX~ and ~\text{query_bigger}(IDX)~ returns the minimum ~\min(DP_{k, j-1} + A_k)~ for all indices greater than ~IDX~.

Time Complexity: ~\mathcal{O}(N \log(N) K)~