Maximum Difference Between Increasing Elements

🏠 ⬅️ ➡️

Given a 0-indexed integer array nums of size n, find the maximum difference between nums[i] and nums[j] (i.e., nums[j] - nums[i]), such that 0 <= i < j < n and nums[i] < nums[j].

Return the maximum difference. If no such i and j exists, return -1.

Example 1:

Input: nums = [7,1,5,4] Output: 4 Explanation: The maximum difference occurs with i = 1 and j = 2, nums[j] - nums[i] = 5 - 1 = 4. Note that with i = 1 and j = 0, the difference nums[j] - nums[i] = 7 - 1 = 6, but i > j, so it is not valid.

Example 2:

Input: nums = [9,4,3,2] Output: -1 Explanation: There is no i and j such that i < j and nums[i] < nums[j].

Example 3:

Input: nums = [1,5,2,10] Output: 9 Explanation: The maximum difference occurs with i = 0 and j = 3, nums[j] - nums[i] = 10 - 1 = 9.

Constraints:

  • n == nums.length
  • 2 <= n <= 1000
  • 1 <= nums[i] <= 109
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program max_diff
    implicit none

    integer :: n, i, j, diff, max_diff
    integer, dimension(:), allocatable :: nums

    ! read input
    read(*,*) n
    allocate(nums(n))
    do i=1,n
        read(*,*) nums(i)
    end do

    ! find maximum difference
    max_diff = -1
    do i=1,n-1
        do j=i+1,n
            diff = nums(j) - nums(i)
            if (diff > max_diff .and. nums(i) < nums(j)) then
                max_diff = diff
            end if
        end do
    end do

    ! print output
    write(*,*) max_diff

end program max_diff
✅ Compiled
✅ Executed
✅ Correct 
module max_difference
  implicit none
contains
  function find_max_difference(nums) result(max_diff)
    integer, intent(in) :: nums(:)
    integer :: max_diff, i, j

    max_diff = -1
    do i = 1, size(nums) - 1
      do j = i + 1, size(nums)
        if (nums(j) - nums(i) > max_diff .and. nums(i) < nums(j)) then
          max_diff = nums(j) - nums(i)
        end if
      end do
    end do
  end function find_max_difference
end module max_difference

program test_max_difference
  use max_difference
  implicit none
  integer, parameter :: n = 4
  integer :: nums(n) = [7, 1, 5, 4]
  integer :: max_diff

  max_diff = find_max_difference(nums)
  write (*,*) "Max difference: ", max_diff

  nums = [9, 4, 3, 2]
  max_diff = find_max_difference(nums)
  write (*,*) "Max difference: ", max_diff

  nums = [1, 5, 2, 10]
  max_diff = find_max_difference(nums)
  write (*,*) "Max difference: ", max_diff
end program test_max_difference
🌐 Data from online sources 
def min_steps_to_equal_elements(nums):
    min_elem = min(nums)
    steps = 0
    for num in nums:
        steps += (num - min_elem)
    return steps

The algorithm you use to minimize the number of operations is as follows:

  1. Find the minimum element in the array. This can be done using a built-in function (e.g., in C++, std::min_element; in Python, min(); or in JavaScript, Math.min()) or by iterating through the array and keeping track of the minimum element encountered.
  2. Initialize a variable named steps to store the total number of operations needed.
  3. Iterate through the array again, and for each element, subtract the minimum element from the current element, and add the result to steps.
  4. Return steps. The variable steps will store the minimum number of operations required to make all elements equal in the input array.

The idea behind this approach is that we can perform multiple subtractions on each element until they all reach the same value as the minimum element in the array. This guarantees the minimum number of operations possible because making all values equal necessarily means having them all equal to the minimum element in the array. Otherwise, additional operations would be needed to decrease the value of at least one element further.

🌐 Data from online sources 
int min_steps_to_equal_elements(vector<int>& nums) {
    int min_elem = *min_element(nums.begin(), nums.end());
    int steps = 0;
    for(int num : nums) {
        steps += (num - min_elem);
    }
    return steps;
}

The algorithm you use to minimize the number of operations is as follows:

  1. Find the minimum element in the array. This can be done using a built-in function (e.g., in C++, std::min_element; in Python, min(); or in JavaScript, Math.min()) or by iterating through the array and keeping track of the minimum element encountered.
  2. Initialize a variable named steps to store the total number of operations needed.
  3. Iterate through the array again, and for each element, subtract the minimum element from the current element, and add the result to steps.
  4. Return steps. The variable steps will store the minimum number of operations required to make all elements equal in the input array.

The idea behind this approach is that we can perform multiple subtractions on each element until they all reach the same value as the minimum element in the array. This guarantees the minimum number of operations possible because making all values equal necessarily means having them all equal to the minimum element in the array. Otherwise, additional operations would be needed to decrease the value of at least one element further.