Problem Statement |
| | Given an integer sequence a[0], a[1], ..., a[N-1], find a contiguous subsequnce a[i], a[i+1], ..., a[j] such that:
- The length of the subsequence (j-i+1) is at least K.
- The average value in the subsequence (a[i] + a[i+1] + ... + a[j])/(j-i+1) is maximized.
You are given a int[] a containing the original sequence, and an int K. Return a int[] containing exactly two elements. The first element is the first index of the contiguous subsequence described above, and the second element is the last index. Both indices are 0-based. If there are multiple subsequences that satisfy the conditions above, return the longest one among them. If there are still multiple subsequences, return the one among them with the smallest first index.
|
| |
Definition |
| | | Class: | ContiguousSubsequences | | Method: | findMaxAverage | | Parameters: | int[], int | | Returns: | int[] | | Method signature: | int[] findMaxAverage(int[] a, int K) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | a will contain between 1 and 50 elements, inclusive. |
| - | Each element of a will be between 0 and 1000000, inclusive. |
| - | K will be between 1 and number of elements in a, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: {1, 2 } | There are 3 possible contiguous subsequences:
- {1,3}, average = 2.
- {1,3,7}, average = 11/3.
- {3,7}, average = 5.
So {3,7} is the best case. |
|
|
| 1) | |
| | |
| 2) | |
| | | Returns: {0, 0 } | | There is only one possible subsequence - the whole sequence. |
|
|
| 3) | |
| | {381,921,513,492,135,802,91,519} | 1 |
| Returns: {1, 1 } | | When K = 1, we can select the subsequence containing only the maximal elements. |
|
|
| 4) | |
| | {381,921,513,492,135,802,91,519} | 4 |
| Returns: {0, 3 } | |
|
| 5) | |
| | {3,5,7,7,2,5,4,7,7,2,4} | 1 |
| Returns: {2, 3 } | |
|
| 6) | |
| | {3, 1, 3, 3, 3, 1, 3, 3, 3} | 1 |
| Returns: {2, 4 } | |
|
| 7) | |
| | {1, 3, 2, 1, 1, 2, 2, 2, 2} | 3 |
| Returns: {5, 8 } | |
|