Find the Highest Altitude
Intuition\nThe problem is about finding the largest altitude reached after a series of altitude gains. Initially, the altitude is 0, and the gains are cumulativ
# Intuition\nThe problem is about finding the largest altitude reached after a series of altitude gains. Initially, the altitude is 0, and the gains are cumulative changes to the altitude. To find the highest altitude, we need to keep track of the cumulative altitude after each gain and record the maximum value.\n\n# Approach\n1. **Initialize Variables**: \n   - Start with `minAltitude = 0` since the initial altitude is 0, and we are interested in the highest point reached.\n   - A variable `sum` is used to keep track of the cumulative altitude, starting from 0.\n\n2. **Iterate Through the Gain Array**:\n   - For each value in the `gain` array, add it to `sum` (which represents the current altitude).\n   - After updating the altitude, compare it to `minAltitude`. If the current altitude is greater than `minAltitude`, update `minAltitude`.\n\n3. **Return the Result**:\n   - At the end of the loop, return the highest altitude recorded (`minAltitude`).\n\n# Complexity\n- **Time Complexity**: \n   - The algorithm iterates through the `gain` array exactly once. Therefore, the time complexity is **O(n)**, where **n** is the length of the `gain` array.\n\n- **Space Complexity**: \n   - The algorithm uses a constant amount of extra space (`sum` and `minAltitude` variables). Thus, the space complexity is **O(1)**.\n\n# Example\nFor the input `gain = [-5, 1, 5, 0, -7]`:\n\n- Initially, `minAltitude = 0` and `sum = 0`.\n- Iterating through `gain`:\n  - After adding `-5`: `sum = -5`, `minAltitude = max(0, -5) = 0`.\n  - After adding `1`: `sum = -4`, `minAltitude = max(0, -4) = 0`.\n  - After adding `5`: `sum = 1`, `minAltitude = max(0, 1) = 1`.\n  - After adding `0`: `sum = 1`, `minAltitude = max(1, 1) = 1`.\n  - After adding `-7`: `sum = -6`, `minAltitude = max(1, -6) = 1`.\n\nThus, the largest altitude reached is 1.\n\n# Code\n```java []\nclass Solution {\n    public int largestAltitude(int[] gain) {\n        int minAltitude = 0;\n        int sum = 0;\n        for (int i = 0; i < gain.length; i++) {\n            sum = sum + gain[i];\n            minAltitude = Math.max(sum, minAltitude);\n        }\n        return minAltitude;\n    }\n}\n```
['Array', 'Prefix Sum', 'Java']