Bài Toán: Cho một mảng có kích thước N, nhiệm vụ là tìm phần tử lớn nhất trong mảng đã cho.
Ví Dụ:
Input: arr[] = {10, 20, 4} Output: 20 Input : arr[] = {20, 10, 20, 4, 100} Output : 100
Phương Pháp 1: Gán Giá Trị MAX và Duyệt Toàn Bộ Danh Sách
Một trong những cách tiếp cận cơ bản và đơn giản nhất để giải quyết vấn đề này là chỉ cần duyệt qua toàn bộ danh sách và tìm giá trị lớn nhất trong số đó.
Thực hiện theo các bước dưới đây để thực hiện thuật toàn này:
- Tạo một biến max để lưu trữ giá trị lớn nhất trong danh sách
- Khởi tạo max với phần tử đầu tiên đầu tiên của mảng để bắt đầu so sánh.
- Sau đó duyệt qua mảng đã cho từ phần tử thứ hai cho đến cuối,với mỗi phần tử:
- So sánh phần tử hiện tại với max
- Nếu phần tử hiện tại lớn hơn giá trị max, thì hãy thay thế giá trị của giá trị max bằng phần tử hiện tại.
- Cuối cùng, trả về và in giá trị của phần tử lớn nhất của mảng được lưu trữ trong giá trị tối đa.
Dưới đây là việc thực hiện phương pháp trên:
// C++ program to find maximum // in arr[] of size n #include <bits/stdc++.h> using namespace std; int largest(int arr[], int n) { int i; // Initialize maximum element int max = arr[0]; // Traverse array elements // from second and compare // every element with current max for (i = 1; i < n; i++) if (arr[i] > max) max = arr[i]; return max; } // Driver Code int main() { int arr[] = {10, 324, 45, 90, 9808}; int n = sizeof(arr) / sizeof(arr[0]); cout << “Largest in given array is ” << largest(arr, n); return 0; } // This Code is contributed // by Shivi_Aggarwal
Output:
Largest in given array is 9808
Độ phức tạp về thời gian: O (N), để duyệt hoàn toàn Mảng.
Phương pháp 2: Giải pháp đệ quy)
Thuật toán sử dụng đệ quy để duyệt mảng và tìm phần tử lớn nhất.
// C++ program to find maximum // in arr[] of size n #include <bits/stdc++.h> using namespace std; int largest(int arr[], int n, int i) { // last index // return the element if (i == n – 1) { return arr[i]; } // find the maximum from rest of the array int recMax = largest(arr, n, i + 1); // compare with i-th element and return return max(recMax, arr[i]); } // Driver Code int main() { int arr[] = { 10, 324, 45, 90, 9808 }; int n = sizeof(arr) / sizeof(arr[0]); cout << “Largest in given array is ” << largest(arr, n, 0); return 0; } // This Code is contributed by Rajdeep Mallick
Output:
Largest in given array is 9808
Độ phức tạp thời gian: O (N), trong đó N là kích thước của mảng đã cho.
Phương Pháp 3: Sử Dụng Thư Viện
Sử dụng hàm thư viện: Hầu hết các ngôn ngữ đều có hàm tích hợp kiểu max () có liên quan để tìm phần tử tối đa, chẳng hạn như std :: max_element trong C ++. Chúng ta có thể sử dụng hàm này để tìm trực tiếp phần tử tối đa.
Dưới đây là việc thực hiện phương pháp trên:
// C++ program to find maximum in arr[] of size n #include <bits/stdc++.h> using namespace std; // returns maximum in arr[] of size n int largest(int arr[], int n) { return *max_element(arr, arr+n); } int main() { int arr[] = {10, 324, 45, 90, 9808}; int n = sizeof(arr)/sizeof(arr[0]); cout << largest(arr, n); return 0; }
Output:
9808
Độ phức tạp về thời gian: O (N), vì hàm max_element () được tích hợp sẵn mất O (N) thời gian.