Clear Explanation with Easy Linear Scan Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nTraverse through the array and keep track of the altitude at the $i$\'th index.\n\n# Ap
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTraverse through the array and keep track of the altitude at the $i$\'th index.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet us keep track of the heights that the biker can be at throughout their journey. There are ```len(gain) + 1``` different points in the roadtrip (since the start is considered a point as well). Let us create an array ```heights``` of size ```len(gain) + 1``` which represents the altitude of the biker at the $i$\'th point. Initially, the array will be filled with 0\'s. \n\nNow, let use traverse through ```gain```. The altitude at ```heights[i]``` is the change in altitude from the altitude of the previous point in the journey. In other words, ```heights[i+1] = heights[i] + gain[i]```. After traversing through the entire input array, we can return the maximum altitude we come across as our answer. \n\nFor a slight optimization, we could define our result ```res``` to be 0 at the start of the loop and at each iteration, take the maximum between ```res``` and ```heights[i+1]``` and return res in the end. \n\nNote that there is no need to maintain the full array of the heights and we can initialize height to be 0 and keep adding the change in altitudes and then comparing them to res which would increase the memory effiency but this approach is more explicit.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def largestAltitude(self, gain: List[int]) -> int:\n        # Initialze the result and the heights array\n        res = 0\n        heights = [0] * (len(gain) + 1)\n\n        # Iterate through the input array and calculate the altitude\n        # for the i\'th point in the journey\n        for i in range(len(gain)):\n            heights[i+1] = heights[i] + gain[i]\n            # Update res to be the maximum altitude we have seen thus far\n            res = max(res, heights[i+1])\n        \n        return res\n```
['Python3']