🚴 **BEATS 100%** Prefix sum solution with explanation
🚴 Find the Highest Altitude During a Bike Trip🧠 IntuitionThe biker starts at altitude 0. As they travel through different segments, their altitude increases or
# 🚴 **Find the Highest Altitude During a Bike Trip**

## 🧠 **Intuition**
The biker starts at altitude `0`. As they travel through different segments, their altitude increases or decreases based on the values in the `gain` array. Our goal is to find the highest altitude reached during the trip.

The altitude at each step can be computed as:
\[
\text{altitude}[i] = \text{altitude}[i-1] + \text{gain}[i-1]
\]
Instead of storing all altitude values, we only need to track the **current altitude** and **maximum altitude reached**.

---

## 🔍 **Approach**
1. **Initialize**:
   - `maxGain = 0` (tracks highest altitude reached)
   - `totalGain = 0` (tracks current altitude)
2. **Iterate through `gain[]`**:
   - Add `gain[i]` to `totalGain` to update current altitude.
   - Update `maxGain` if `totalGain` is higher than the previous maximum.
3. **Return `maxGain`**.

This approach ensures we compute the answer in a **single pass** without extra storage.

---

## ⏳ **Complexity Analysis**
- **Time Complexity:** \( O(n) \) (We iterate through the `gain` array once)
- **Space Complexity:** \( O(1) \) (Only a few integer variables are used)

---

## 📜 **C++ Solution**
```cpp []
class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int maxGain = 0;
        int totalGain = 0;
        for(int i = 0; i < gain.size(); i++) {
            totalGain += gain[i];
            maxGain = max(maxGain, totalGain);
        }
        return maxGain;
    }
};
```
```java []
class Solution {
    public int largestAltitude(int[] gain) {
        int maxGain = 0;
        int totalGain = 0;
        for (int i = 0; i < gain.length; i++) {
            totalGain += gain[i];
            maxGain = Math.max(maxGain, totalGain);
        }
        return maxGain;
    }
}
```
```python []
class Solution:
    def largestAltitude(self, gain):
        maxGain = 0
        totalGain = 0
        for g in gain:
            totalGain += g
            maxGain = max(maxGain, totalGain)
        return maxGain
```
```javascript []
var largestAltitude = function(gain) {
    let maxGain = 0, totalGain = 0;
    for (let g of gain) {
        totalGain += g;
        maxGain = Math.max(maxGain, totalGain);
    }
    return maxGain;
};
```
## 📊 Example Walkthrough
### Example 1
Input:
```plaintext
gain = [-5, 1, 5, 0, -7]
```
Altitude Calculation
```
Step	Gain	Altitude
Start	 —	     0
+(-5)	-5	     0 → -5
+1	    -4	    -5 → -4
+5	     1	    -4 → 1 ✅ (New max)
+0	     1	     1 → 1
-7	    -6	     1 → -6
```
```
Output: 1
```
### Example 2
Input:
```plaintext
gain = [-4, -3, -2, -1, 4, 3, 2]
```
Altitude Calculation
```
Step	Gain	Altitude
Start	 —	     0
-4	    -4	     0 → -4
-3	    -7	    -4 → -7
-2	    -9	    -7 → -9
-1	    -10	    -9 → -10
+4	    -6	    -10 → -6
+3	    -3	    -6 → -3
+2	    -1	    -3 → -1
```
```
Output: 0
```
# ✅ Key Takeaways
1. Efficient computation with just one loop.

2. No extra space used (constant space complexity).

3. Iterate once and track the highest altitude in real-time.

🚀 Optimized for large inputs!


['Array', 'Prefix Sum', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']