<center>
</center>
Let’s say you have a line of candy pieces, and each piece has a certain number of calories:
Candy Line: [2, 5, 1, 8, 3] (These numbers represent the calories in each candy piece)
**What’s a “prefix sum”?**
A prefix sum is like creating a new line of numbers where each number tells you the total calories of all the candy pieces up to that point.
Here’s how we build the prefix sum line:
1. **First Piece:** The first number in the prefix sum line is the same as the first number in the candy line: 2.
2. **Second Piece:** The second number is the first number plus the second number: 2 + 5 = 7.
3. **Third Piece:** The third number is the first plus the second plus the third: 2 + 5 + 1 = 8.
4. **Fourth Piece:** The fourth number is the first plus the second plus the third plus the fourth: 2 + 5 + 1 + 8 = 16.
5. **Fifth Piece:** The fifth number is the first plus the second plus the third plus the fourth plus the fifth: 2 + 5 + 1 + 8 + 3 = 19.
So, the prefix sum line looks like this:
> Prefix Sum Line: [2, 7, 8, 16, 19]
# Understanding the problem
There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.
You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.
**Example 1:**
```
Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.
```
**Example 2:**
```
Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.
```
**Constraints:**
- n == gain.length
- 1 <= n <= 100
- -100 <= gain[i] <= 100
# Solutions
## Python
```
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
sum_so_far = 0
prefix_nums = [0]
for num in gain:
sum_so_far += num
prefix_nums.append(sum_so_far)
return max(prefix_nums)
```
## Go
```
func largestAltitude(gain []int) int {
sumSoFar := 0
prefixNums := []int{0}
for _, num := range gain {
sumSoFar += num
prefixNums = append(prefixNums, sumSoFar)
}
maxAltitude := 0
for _, altitude := range prefixNums {
if altitude > maxAltitude {
maxAltitude = altitude
}
}
return maxAltitude
}
```
## Typescript
```
function largestAltitude(gain: number[]): number {
let sumSoFar = 0;
const prefixNums = [0];
for (const num of gain) {
sumSoFar += num;
prefixNums.push(sumSoFar);
}
return Math.max(...prefixNums);
}
```
## Rust
```
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
sum_so_far = 0
prefix_nums = [0]
for num in gain:
sum_so_far += num
prefix_nums.append(sum_so_far)
return max(prefix_nums)
```
# Explanation
Start at Zero: You begin your hike at zero altitude.
**Keep a Running Total:**
- As you take each step (read each number in the list), you add that number to your current altitude.
- This running total represents your altitude at that exact moment.
**Record Each Altitude:**
- After each step, you write down your current altitude. This creates a list of all the altitudes you’ve reached along the way.
**Find the Highest Point:**
- Once you’ve finished the hike (gone through all the numbers), you look at the list of altitudes you recorded.
- You find the biggest number in that list. That number is the highest altitude you reached during your hike.
**Why This Works (Prefix Sum Concept):**
- Each altitude you record is the sum of all the altitude changes up to that point. This is the “prefix sum” idea — you’re calculating the sum of the “prefix” (the beginning portion) of your altitude changes.
- By keeping track of all these running sums (altitudes), you make it easy to see the highest point you reached.
>You’re just adding up the altitude changes as you go, writing down your altitude at each step, and then finding the biggest altitude you wrote down.
---
*If you liked this article I’d appreciate a clap or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.*
*Muchas gracias!*
*Follow me for more content like this.*
*[X](https://twitter.com/edca3911) | [PeakD](https://peakd.com/@simplestack) | [Rumble](https://rumble.com/user/simplestack) | [YouTube](https://www.youtube.com/@simple-stack-by-ed) | [Linked In](https://www.linkedin.com/in/edwardcasanova/) | [GitHub](https://github.com/ed3899) | [PayPal.me](https://paypal.me/edca3899?country.x=MX&locale.x=es_XC)*
*Down below you can find other ways to tip my work.*
```
BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"
```
hiveblocks