Welcome to Subscribe On Youtube
1732. Find the Highest Altitude
Description
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
Solution 1: Prefix Sum (Difference Array)
We assume the altitude of each point is $h_i$. Since $gain[i]$ represents the altitude difference between the $i$th point and the $(i + 1)$th point, we have $gain[i] = h_{i + 1}  h_i$. Therefore:
\[\sum_{i = 0}^{n1} gain[i] = h_1  h_0 + h_2  h_1 + \cdots + h_n  h_{n  1} = h_n  h_0 = h_n\]which implies:
\[h_{i+1} = \sum_{j = 0}^{i} gain[j]\]We can see that the altitude of each point can be calculated through the prefix sum. Therefore, we only need to traverse the array once, find the maximum value of the prefix sum, which is the highest altitude.
In fact, the $gain$ array in the problem is a difference array. The prefix sum of the difference array gives the original altitude array. Then find the maximum value of the original altitude array.
The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array gain
.

class Solution { public int largestAltitude(int[] gain) { int ans = 0, h = 0; for (int v : gain) { h += v; ans = Math.max(ans, h); } return ans; } }

class Solution { public: int largestAltitude(vector<int>& gain) { int ans = 0, h = 0; for (int v : gain) h += v, ans = max(ans, h); return ans; } };

class Solution: def largestAltitude(self, gain: List[int]) > int: return max(accumulate(gain, initial=0))

func largestAltitude(gain []int) (ans int) { h := 0 for _, v := range gain { h += v if ans < h { ans = h } } return }

/** * @param {number[]} gain * @return {number} */ var largestAltitude = function (gain) { let ans = 0; let h = 0; for (const v of gain) { h += v; ans = Math.max(ans, h); } return ans; };

class Solution { /** * @param Integer[] $gain * @return Integer */ function largestAltitude($gain) { $max = 0; for ($i = 0; $i < count($gain); $i++) { $tmp += $gain[$i]; if ($tmp > $max) { $max = $tmp; } } return $max; } }

impl Solution { pub fn largest_altitude(gain: Vec<i32>) > i32 { let mut ans = 0; let mut h = 0; for v in gain.iter() { h += v; ans = ans.max(h); } ans } }