Неправильный ответ на вопрос о hackerrank
Given a set of arrays of size and an integer , you have to find the maximum integer for each and every contiguous subarray of size for each of the given arrays. Input Format First line of input will contain the number of test cases T. For each test case, you will be given the size of array N and the size of subarray to be used K. This will be followed by the elements of the array A . Constraints , where is the element in the array . Output Format For each of the contiguous subarrays of size of each array, you have to print the maximum integer. Sample Input i 2 5 2 3 4 6 3 4 7 4 3 4 5 8 1 4 10 Sample Output 4 6 6 4 8 8 8 10 Explanation For the first case, the contiguous subarrays of size 2 are {3,4},{4,6},{6,3} and {3,4}. The 4 maximum elements of subarray of size 2 are: 4 6 6 4. For the second case,the contiguous subarrays of size 4 are {3,4,5,8},{4,5,8,1},{5,8,1,4} and {8,1,4,10}. The 4 maximum element of subarray of size 4 are: 8 8 8 10.
Я борюсь с вопросом о хакерранке. Я реализовал алгоритм, который находит максимальный элемент в окнах и сохраняет его индекс, а затем использует этот индекс максимального элемента в предыдущем окне, чтобы найти максимальный элемент в следующем окне только в том случае, если индекс максимального элемента лежит между индексами следующего окна. Я пробовал много тестовых случаев, но все еще не могу понять ошибку в коде.
Что я уже пробовал:
using namespace std; #include<iostream> #include<algorithm> int m,idx,ct=0; void maxinwindow(int arr[], int start, int end) { /*If the index of the maximum element in the previous window is between the indexes of next windows then no need to compare elements that were in previous window */ if(idx>=start) { if(arr[idx]>=arr[end]) { if(arr[idx]==arr[end]) { idx=end; } //ct++; m=arr[idx]; } else { //ct++; m=arr[end]; idx=end; } } else { if(arr[start]>=arr[start+1]) { //ct++; m=arr[start]; } else { //ct++; m=arr[start+1]; } for(int k=start+2;k<=end;k++) { //ct++; if(arr[k]>=m) { m=arr[k]; idx=k; } } } } int main() { int arr[100000]; int q; cin>>q; for(int i=1,size,ws;i<=q;i++) { m=0;ct=0; cin>>size; //Array size cin>>ws; //Window Size //Entering The Elements In The Array for(int j=1;j<=size;j++) { cin>>arr[j]; } //Boundary Condition i.e. Windows size is equal to 1 if(ws==1) { for(int j=1;j<=size;j++) { cout<<arr[j]<<" "; } } else { for(int k=1;k<=ws;k++) { //ct++; if(arr[k]>=m) { m=arr[k]; idx=k; } } //ct--; cout<<m<<" "; for(int k=2,j;k<=(size-(ws-1));k++) { j=(k+(ws-1)); maxinwindow(arr,k,j); cout<<m<<" "; } cout<<endl; } } }
CPallini
Я полагаю, вы должны сообщить точные требования, так как ранг хакера недоступен для тех немногих из нас, кто не хочет подписаться.
Shantanu Dwivedi
да, конечно.
Patrice T
Добавление ваших неправильных результатов для примеров может помочь нам понять, насколько это неправильно.
CPallini
Я вижу (спасибо Патрис) он предназначен как упражнение на std::deque. Тогда почему (свежий ад) вы не используете std::deque?
Shantanu Dwivedi
я могу, но я хочу знать, что не так с этим алгоритмом.
Patrice T
Я просто нажимаю на крестик в правом верхнем углу, чтобы закрыть экран подписи.
CPallini
:-О