Problem link : contest
practice
Difficulty : Cakewalk
Pre-requisites : AD-hoc
Solution :
The subsequence which will have maximum possible average will be made only of elements having values equal to maximum value in the array.
So the answer of the problem will be to find the maximum possible value in an array which can be done in a single iteration of the array or by sorting the
array and picking the last element of the array.
Complexity of iteration based solution will be O(N) while that of sortin based will be O(n log n).
Pseudo Code 1
ans = 0;
for (i = 0; i < n; i++)
ans = max(ans, a[i]);
Pseudo Code 2
sort the array.
ans = a[n - 1] // Assuming array is 0 index based.
Tester’s solution: link