Chương trình tìm số lượng tối đa trong danh sách được xoay trong C ++

Giả sử có một mảng và được sắp xếp, hãy coi mảng đó được xoay ở một trục nào đó mà chúng ta chưa biết. Vì vậy, chúng ta phải tìm giá trị lớn nhất từ ​​mảng đã quay đó. Vì vậy, nếu mảng giống như [3,4,5,1,2], thì đầu ra sẽ là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• low:=0 and high:=chỉ số cuối cùng của mảng, n:=kích thước của mảng, ans:=0

• trong khi thấp <=cao

  • giữa:=low + (cao - thấp) / 2

  • nếu arr [low]

  • else if arr [high]> arr [mid], then ans:=Maximum of ans and arr [mid], high:=mid - 1

  • else if low =mid, then ans:=Maximum of ans and arr [low], low:=mid + 1

  • else if high =mid, then ans:=Maximum of ans and arr [high], high:=mid - 1

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int search(vector <int>& arr, int low, int high){
      if(low == high){
         return arr[low];
      }
      int mid = low + (high - low) / 2;
      int ans = 0;
      if(arr[low] < arr[mid]){
         ans = max(arr[low], search(arr, mid, high));
      }
      else if (arr[high] > arr[mid]){
         ans = max(arr[mid], search(arr, low, mid));
      }
      else if(arr[low] == arr[mid]){
         ans = max(arr[low], search(arr, low + 1, high));
      }
      else if(arr[high] == arr[mid]){
         ans = max(arr[high], search(arr, low, high - 1));
      }
      return ans;
   }
   int findMax(vector<int>& nums) {
      return search(nums, 0, nums.size() - 1);
   }
};
main(){
   Solution ob;
   vector<int> v = {4,5,5,5,6,8,2,3,4};
   cout <<(ob.findMax(v));
}

Đầu vào

[4,5,5,5,6,8,2,3,4]

Đầu ra

8