Professor McGonagall asks you to help her with some arrays that are spiked. A sp
ID: 3885467 • Letter: P
Question
Professor McGonagall asks you to help her with some arrays that are spiked. A spiked array has the property that the subarray A[1...i] has the property that A[j] < A[j + 1] for 1 j < i, and the subarray A[i...n] has the property that A[j] > A[j + 1] for i j < n. Using her wand, McGonagall writes the following spiked array on the board A = [7; 8; 10; 15; 16; 23; 19; 17; 4; 1], as an example.
(d) Suppose that k = 2 and we can guarantee that neither spike is closer than n=4 positions to the middle of the array, and that the "joining point" of the two singly-spiked subarrays lays in the middle half of the array. Now write an algorithm that returns the maximum element of A in sublinear time. Prove that your algorithm is correct, give a recurrence relation for its running time, and solve for its asymptotic behavior.
Explanation / Answer
Algorithm:
if(a[pos]>a[pos+1]&&a[pos]>a[pos-1]){
max=a[pos];
}
else if(a[pos]<a[pos+1]){
i=pos;
while(i<n-1){
if(a[i+1]<a[i]){
max=a[i];
break;
}
i++;
}
if(i= =n-1)
max=a[n-1];
}
else ifa[pos]<a[pos-1]){
i=pos;
while(i>0){
if(a[i-1]<a[i]){
max=a[i];
break;
}
i--;
}
if(i==0)
max=a[0];
}
java program:
import java.util.*;
public class max_subarray{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] a=new int[n];
for(int i=0;i<n;i++)
a[i]=in.nextInt();
int pos=n/2;
int max=-1;
if(pos>0&&pos<n-1&&a[pos]>a[pos+1]&&a[pos]>a[pos-1]){
max=a[pos];
}
else if(pos<n-1&&a[pos]<a[pos+1]){
int i=pos;
while(i<n-1){
if(a[i+1]<a[i]){
max=a[i];
break;
}
i++;
}
if(i==n-1)
max=a[n-1];
}
else if(pos>0&&a[pos]<a[pos-1]){
int i=pos;
while(i>0){
if(a[i-1]<a[i]){
max=a[i];
break;
}
i--;
}
if(i==0)
max=a[0];
}
System.out.println(max);
}
}
output:
10
7 8 10 15 16 23 19 17 4 1
1
23
It has 3 cases
we start from the middle
as the first array is in increasing order and second is in decreasing order the maximum element may be at middle
or to left of mid or right of mid.
The time comlexity in worst case is O(n/2) as we strart from middle in worst case we have to check half array to find the maximum element
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.