Find the Highest Altitude

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: gain
    integer :: i

    ! Examples
    gain = [-5, 1, 5, 0, -7]
    call solve(gain)
    gain = [-4, -3, -2, -1, 4, 3, 2]
    call solve(gain)

contains

    subroutine solve(gain)
        implicit none
        integer, intent(in) :: gain(:)
        integer :: altitude

        altitude = 0
        do i = 1, size(gain)
            altitude = max(altitude, altitude + gain(i))
        end do
        write (*, '(I0)') altitude
    end subroutine solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module highest_altitude
    implicit none
    contains
    function highest_altitude(gain) result(highest)
        integer, intent(in) :: gain(:)
        integer :: highest, altitude, i

        altitude = 0
        highest = 0

        do i = 1, size(gain)
            altitude = altitude + gain(i)
            if (altitude > highest) then
                highest = altitude
            end if
        end do
    end function highest_altitude
end module highest_altitude

program test_highest_altitude
    use highest_altitude
    implicit none
    integer :: gain(5)

    ! Example 1:
    gain = [-5, 1, 5, 0, -7]
    write (*, '(A, I0)') 'Example 1: ', highest_altitude(gain)

    ! Example 2:
    gain = [-4, -3, -2, -1, 4, 3, 2]
    write (*, '(A, I0)') 'Example 2: ', highest_altitude(gain)
end program test_highest_altitude
🌐 Data from online sources 
def min_operations(n):
    operations = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        operations += 1
    return operations

The algorithm initializes a variable operations to store the number of operations taken. It then enters a loop that iterates while n is greater than 0. In each iteration, it checks whether n is divisible by 2 (i.e., even). If it is, the algorithm divides n by 2; otherwise, it decrements n by 1. In each loop iteration, the algorithm also increments the operations counter. The loop ends when n reaches 0, and the algorithm returns the total count of operations performed.

This algorithm finds the minimum number of operations required because dividing n by 2 is more optimal than decrementing n by 1 whenever n is even, as it reduces the number more rapidly.

🌐 Data from online sources 
int min_operations(int n) {
    int operations = 0;
    while (n > 0) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n--;
        }
        operations++;
    }
    return operations;
}

The algorithm initializes a variable operations to store the number of operations taken. It then enters a loop that iterates while n is greater than 0. In each iteration, it checks whether n is divisible by 2 (i.e., even). If it is, the algorithm divides n by 2; otherwise, it decrements n by 1. In each loop iteration, the algorithm also increments the operations counter. The loop ends when n reaches 0, and the algorithm returns the total count of operations performed.

This algorithm finds the minimum number of operations required because dividing n by 2 is more optimal than decrementing n by 1 whenever n is even, as it reduces the number more rapidly.