Here’s a python programming challenge for you to help you develop your problem solving and algorithmic thinking skills.
Find the position of the maximum value in a Python list of integers.
Some of you may know that Python has a function
max() to do this for you, but I want you to think about how you would implement this function for yourself.
Here’s an example:
You can see from the image that the highest peak is the value 9 at position 3. Being really clear about whether you are considering the position vs the value of an item in a list is really important and can save you a lot of mental effort and time spent debugging compared to if you mix up the two things in you thinking. There is an article about this here, which you may find helpful.
For the purposes of this exercise, assume your list contains non-negative integers. Some ingredients you will need to tackle this challenge are
- Looping thorough a list
- Accessing the values in a list at a given index
- Selection (
- Comparison (probably
If you are not very strong with these foundations, you may want revise them before attempting this challenge. There are a great many resources on the internet you could use for this. One I think you would find particularly helpful is Hour of Python.
Before writing any actual code, have a think about how you will approach the problem. Make some notes, maybe on paper or even in a blank Python file as comments (
# This is a Python comment). This second option is a great way to approach these kinds of problem, as you get to think about ingredients of the solution as well as getting a basic draft of the structure for free. Once you have these comments, you can begin to write your solution as actual code underneath each comment. (You may of course have to move things around bit from your initial “draft” solution.)
You can see an example of what these comments might look like by clicking “Show solution” below. Do try to outline the algorithm yourself before looking though.
# Think about any variables you will need
# Assume the first item is the maximum to begin with
# Keep track of the position of the maximum value
# Loop through the remaining items and compare with the maximum so far (what do you call that variable?)
# If the current value is greater, update the maximum position variable
Depending on your level of experience with Python programming, this challenge may be easy or rather hard. That’s fine. Just do what you can and when you’ve either got a solution or tried as hard as you want to, check out my solution below.
To keep you focused, have a specific example in mind for this exercise.
For example, define
arr = [2, 3, 1, 9, 6, 8] and write code to find the maximum value in this list, which is
9 in position
3. Some versions of this exercise want the actual value (which would be the
9 here), but here I want you to find the position of the highest value. If there is more than one instance of the highest value, finding just one of the positions where it occurs in the list is fine. Once you have a solution, be sure to check with some more example lists too.
Find the Global Maximum of a List with Python
arr = [2, 3, 1, 9, 6, 8] pos_of_max = 0 for i in range(1, len(arr)): if arr[i] > arr[pos_of_max]: pos_of_max = i print(pos_of_max)
And here is a version using a function along with some basic tests using Python’s
def find_global_maximum(arr): length = len(arr) if length < 1: return None pos_of_max = 0 for i in range(1, len(arr)): if arr[i] > arr[pos_of_max]: pos_of_max = i return pos_of_max arr =  assert find_global_maximum(arr) is None arr =  assert find_global_maximum(arr) == 0 arr = [2, 3, 1, 9, 6, 8] assert find_global_maximum(arr) == 3 arr = [1, 2, 3, 4, 5, 0] assert find_global_maximum(arr) == 4 arr = [1, 2, 3, 3, 2] assert find_global_maximum(arr) == 2 # The algorithm checks from left to right, so the fist instance is returned.
For those of you who know about linear search and time complexity, this algorithm has the same time complexity as the worst case of linear search, where the target item is at the end of the list. This level of time complexity is technically referred to as
O(n)(but don’t worry at all about that if you haven’t studied time complexity yet). The algorithm must check the whole list to “be sure” that the maximum value has been found.
With just the unsorted array, there is no way to find the maximum any faster. Since you don’t know which element is the largest and smallest, you have to look at them all. However, if we sort the list first, using an efficient sorting algorithm such as merge sort, then finding the maximum value becomes as simple as finding the last item in the sorted list.
This version can be implemented like so:
arr = [2, 3, 1, 9, 6, 8] arr = sorted(arr) print("The sorted list is", arr) print("The maximum value is at position", str(len(arr) - 1))
I hope you found this challenge interesting and helpful. Happy computing!