1.5.12 배열 인덱스의 최대 차이 구하기
문제 1-12 주어진 배열 arr[]에서 arr[j] > arr[i]인 인덱스 j와 i의 최대 차이를 구하세요.
첫 번째 해결책 무차별 대입으로 각 인덱스 i에 대해 arr[j] > arr[i]인 인덱스 j를 찾습니다. 2개의 반복문을 사용하는데, 하나는 인덱스 i를 선택하기 위한 반복문이고 다른 하나는 배열의 인덱스 i+1부터 배열의 크기까지 순회하는 반복문입니다.
해결책 1-12-1
int ArrayIndexMaxDiff(int arr[], int size) { int maxDiff = -1; int j; for (int i = 0; i <size; i++) { j = size - 1; while (j > i) { if (arr[j] > arr[i]) { maxDiff = max(maxDiff, j-i); break; } j -= 1; } } return maxDiff; }
분석 시간 복잡도는 O(n2)이며, 공간 복잡도는 O(1)입니다.