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:

1Input: gain = [-5,1,5,0,-7]
2Output: 1
3Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Example 2:

1Input: gain = [-4,-3,-2,-1,4,3,2]
2Output: 0
3Explanation: 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

Solution

This is direct prefixSum with highest value in the prefix sum array being the output. In this case, we can save some space by actually not calculating prefixSum, but keeping track of the highest value we get for that array.

 1class Solution {
 2    public int largestAltitude(int[] gain) {
 3        int max = 0; // we start at 0
 4        int current = 0;
 5        for (int i = 0; i < gain.length; i++) {
 6            current += gain[i];
 7            if (current > max) {
 8                max = current;
 9            }
10        }
11        return max;
12    }
13}