BEST SOLUTION BEATING 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nIt find the largest altitude reached by accumulating the gains at each step from an ini
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt find the largest altitude reached by accumulating the gains at each step from an initial altitude of zero. The gain array represents the gain or loss in altitude at each step of a journey. The task is to find the maximum altitude reached during the journey.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nInitialize an array arr of size n+1, where n is the length of the gain array. This array arr is used to keep track of the altitude after each step.\nIterate through the gain array and calculate the altitude after each step by accumulating the gains/losses. Store these altitudes in the arr array.\nFind the maximum altitude reached by iterating through the arr array and keeping track of the maximum value found.\n\n# Complexity\n**Time Complexity:**\nInitializing the arr array takes O(n) time, where n is the length of the gain array.\nThe first loop to calculate altitudes from gains takes O(n) time since it iterates through the gain array.\nThe second loop to find the maximum altitude also takes O(n) time as it traverses the arr array.\nOverall, the time complexity of the code is O(n).\n\n**Space Complexity:**\nAn additional array arr of size n+1 is used, resulting in O(n) space complexity, where n is the length of the gain array.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int largestAltitude(int[] gain) {\n        int n=gain.length;\n        int[] arr=new int[n+1];\n        for(int i=1;i<arr.length;i++){\n            arr[i]=arr[i-1]+gain[i-1];\n        }\n        int m=0;\n        for(int i=0;i<arr.length;i++){\n            if(m<arr[i])\n                m=arr[i];\n        }\n        return m;\n        \n        \n    }\n}\n```
['Array', 'Prefix Sum', 'Java']