Consider the following program: int f (int * p, int n) { if (n <= 1) return 0;…
2016
Consider the following program:
int f (int * p, int n) { if (n <= 1) return 0; else return max (f (p+1, n-1), p[0] - p[1]); } int main () { int a[] = {3, 5, 2, 6, 4}; printf(" %d", f(a, 5)); }
Note:max(x,y)returns the maximum of x and y.
The value printed by this program is .
Attempted by 72 students.
Show answer & explanation
Correct answer: 3
Answer: 3
Explanation: The function returns the maximum between the recursive result for the remainder of the array and the difference between the first two elements of the current subarray. Because the base case returns 0 when there is at most one element, the final result is the maximum of 0 and all adjacent differences a[i] - a[i+1] for i = 0..n-2.
Base case: when n <= 1 the function returns 0.
Compute the adjacent differences for the array {3, 5, 2, 6, 4}:
a[0] - a[1] = 3 - 5 = -2
a[1] - a[2] = 5 - 2 = 3
a[2] - a[3] = 2 - 6 = -4
a[3] - a[4] = 6 - 4 = 2
Recursively the function propagates the maximum of these differences (and 0). The values encountered during recursion are 0, then 2, then 2, then 3, then finally 3.
Therefore the maximum among 0 and all adjacent differences is 3, so the program prints 3.
A video solution is available for this question — log in and enroll to watch it.