배열의 최대 차이

오늘은 배열의 최대 차이를 살펴보겠습니다.
문제

find the maximum difference in the array array[j] - array[i],where j>i

우리는 이것을 사용하여 해결할 수 있습니다

O(n2) 2 for 루프 방법

O(n) 효율적인 솔루션

첫 번째를 살펴 보겠습니다

int maxDif(int[] arr) {
    int maxDif = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] - arr[i] > maxDif) {
          maxDif = arr[j] - arr[i];
        }
      }
    }
    return maxDif;
  }

우리는 maxDif 변수를 생성하고 다음과 같이 초기화할 것입니다.Integer.MIN_VALUE다음으로 for 루프(i 루프)를 사용하여 배열을 반복할 것입니다.
그 i 루프 내부에서 j>i 조건으로 인해 오른쪽에 있는 모든 요소를 ​​반복할 것입니다. i+1로 j 루프를 시작할 것입니다. 각 요소에 대해 차이점을 찾을 것입니다. 그 차이는 우리가 그 값을 할당할 maxDif보다 큽니다.

Time complexity:- O(n²)

다른 방법을 알아보자

int maxDifEfficient(int[] arr) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length - 1; i++) {
      max = Math.max(max, arr[i + 1]); 
      min = Math.min(min, arr[i]);
    }
    return max - min;
  }

이 방법의 논리는 가장 큰 숫자와 가장 작은 숫자 사이에서 빼면 최대 차이가 가능하다는 것입니다.
따라서 j>i 조건의 배열에서 가장 큰 수와 가장 작은 수를 찾아야 합니다.
여기서 우리는 값이 각각 Integer.MAX_VALUE, Integer.MIN_VALUE인 최소 및 최대 변수를 사용하는 O(n)의 문제를 해결하려고 합니다.
최대값과 최소값인 배열 찾기를 반복합니다.

Math.max(max,arr[i+1])를 사용하여 최대값을 찾습니다. 여기서 j는 i+1입니다. i+1이 i보다 크기 때문에 j>i 조건을 만족합니다.

Math.min(min,arr[i])를 사용하여 최소값을 찾습니다.

루프가 완료되면 j>i 조건과 관련하여 배열에서 가장 큰 수와 가장 작은 수를 갖게 되며 최대 차이를 찾기 위해 이를 뺄 수 있습니다.

Time complexity:- O(n²)