A maximum is the greatest value in a collection according to its ordering. In an array, find it by scanning each element and updating the stored value when a larger one appears. section 2.16
Two practical ways to locate a maximum are:
- In an array, initialize the candidate from the first element, compare later elements against it, and retain the value and index. section 2.16
- In a binary search tree, start at the root and follow right-child links until reaching a node with no right child. section 11.9
- For a tree node, apply the same rightward traversal to find the maximum of its subtree and return the node with its parent. section 11.9
Die-roll counters
After recording die rolls in six counters, scan the counters to find the most frequent face. Return both the counter's value and its index; adjust the index by one to name the die face. section 2.16
Replacing a deleted tree node
When deleting a BST node with two children, replace its value with the maximum of its left subtree. That predecessor can then be removed through a simpler deletion case. section 11.11
def max_in_array(array):
if len(array) == 0:
raise Exception('Max of an empty array')
max_index = 0
for index in range(1, len(array)):
if array[index] > array[max_index]:
max_index = index
return max_index, array[max_index]
The implementation scans an array, rejects an empty input, tracks the maximum index, and returns both the index and value. section 2.16
