C++ | Linear Scan or Iterative |
Intuition\n Describe your first thoughts on how to solve this problem. My initial thoughts on solving this problem would be as follows:\n\n1. Initialize two var
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->My initial thoughts on solving this problem would be as follows:\n\n1. Initialize two variables, `altitude` and `max`, to 0. These will be used to keep track of the current altitude and the maximum altitude reached during the journey, respectively.\n\n2. Iterate through the given `gain` vector. At each step, update the `altitude` by adding the gain at the current step.\n\n3. Check if the updated `altitude` is greater than the current maximum altitude (`max`). If it is, update `max` with the new value of `altitude`.\n\n4. After iterating through all the elements in the `gain` vector, `max` will hold the maximum altitude reached during the journey.\n\n5. Return the value of `max` as the result.\n\nThis approach calculates the altitude at each step of the journey and keeps track of the maximum altitude achieved so far. By the end of the journey, it will have the maximum altitude reached.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->This approach calculates the altitude at each step of the journey by summing up the gains. It then updates the maximum altitude if a higher altitude is encountered. By the end of the journey, the maximum altitude reached is returned as the result.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> O(n) \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ --> O(1) \n\n# Code\n```\nclass Solution {\npublic:\n    int largestAltitude(vector<int>& gain)\n     {   \n        int altitude=0,max=0;\n        for(int i=0;i<gain.size();i++)\n        {\n            altitude=altitude+gain[i]; // Increase the altitude by the gain at each step\t\n            if(max<altitude)\n                max=altitude; // Update the maximum altitude if the current altitude is higher\n        }\n        return max; // Return the maximum altitude\n    }\n};\n\n```\n![Leetcode.jpeg](https://assets.leetcode.com/users/images/10ec509d-3666-4719-94b0-6ab27f0a2c65_1687157902.970192.jpeg)\n
['Array', 'Dynamic Programming', 'Iterator', 'Prefix Sum', 'C++']