Problem Statement |
| | A sequence of numbers is called strictly monotonically increasing if every term of the sequence is strictly greater than the one preceding it. Simliarly, a sequence is called strictly monotonically decreasing if every term is strictly less than the one preceding it. A strictly monotonic sequence is a sequence that is either strictly monotonically increasing or decreasing. A sequence of integers is called k-monotonic if it can be decomposed into k disjoint contiguous subsequences that are strictly monotonic.
For example a strictly monotonically increasing sequence is 1-monotonic---in fact it is k-monotonic for every k between 1 and the number of elements it contains. The sequence {1, 2, 3, 2, 1} is 2-monotonic since it can be decomposed into {1, 2, 3} and {2, 1}.
If a sequence is not k-monotonic, you can transform it into a k-monotonic sequence by performing the following operation one or more times: select any term in the sequence and either increase it or decrease it by one. You are allowed to perform any number of these operations on any of the terms. Given a int[] sequence and an int k, return the minimum number of operations required to transform the given sequence into a k-monotonic sequence. |
| |
Definition |
| | | Class: | KMonotonic | | Method: | transform | | Parameters: | int[], int | | Returns: | int | | Method signature: | int transform(int[] sequence, int k) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | In the context of this problem, a subsequence of length M consists of M consecutive elements of the original sequence. |
| |
Constraints |
| - | sequence will contain between 1 and 50 elements, inclusive. |
| - | Each element of sequence will be between -20,000,000 and 20,000,000, inclusive. |
| - | k will be between 1 and the number of elements in sequence, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 4 | | You can transform this into {0,1,2,3} using 4 operations. Decrease the first term by 1 to get 0, increase the third term by 1 to get 2, and increase the fourth term by 1 twice to get 3. Other possibilities are {-1,0,1,2}, {2,1,0,-1} and {3,2,1,0}. |
|
|
| 1) | |
| | | Returns: 2 | | Some optimal solutions: {1,2,2,1} {1,0,0,1} {1,2,1,2} {1,0,1,2}. |
|
|
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | | Returns: 6 | | You can transform this into {0,1,2,3,4,5} |
|
|
| 5) | |
| | {1,10,4,2,5,1,3,2,4,6,1} | 3 |
| Returns: 11 | | Transform this into {1,10,3,4,5,1,2,3,4,6,7} which can be decomposed into {1,10} {3,4,5} and {1,2,3,4,6,7}. |
|
|
| 6) | |
| | {-913,-4158,-146,-2625,-2926,3071,297,4049,-4566,3581,-2070,-1794,1953,4434,4351,-710,-3124,2148,1192,1802,644} | 8 |
| Returns: 611 | |
|