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 | PeakD | Rumble | YouTube | Linked In | GitHub | PayPal.me

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"