The algorithm below computes the maximum value in an array A[1.n] with n element

Question

The algorithm below computes the maximum value in an array A[1.n] with n elements: COMPUTE-MAX(A,n) for i = n-1 downto 1 if Ali>max max = A[i] return max Which of the following is the correct loop invariant of the for loop? At the start of each iteration i of the for loop, max is the maximum value in the subarray Ali.n]. OAt the start of each iteration i of the for loop, max is the maximum value in the subarray A[1 i-1 At the start of each iteration i of the for loop, max is the maximum value in the subarray A[1.n]. At the start of each iteration i of the for loop, max is the maximum value in the subarray A[1..]. At the start of each iteration i of the for loop, max is the maximum value in the subarray Ali+1.n]

Explanation / Answer

1. At the start of each iteration i of the for loop, max is the maximum value in the subarray A[i,n].
As you can see, i is initialized with the value n-1.
So, this subarray becomes A[n-1,n]. It is checking only last two elements. So, This is not a proper for loop variant.

2. At the start of each iteration i of the for loop, max is the maximum value in the subarray A[1,i-1].
By replacing value of i, it becomes A[1,n-2], so it isn't checking for max in last 2 elements{n-1 and n}.
So, This is not a proper for loop variant.

3. At the start of each iteration i of the for loop, max is the maximum value in the subarray A[1,n].
As you can see, max is initialized with A[n], i.e, last element value. In the for loop iterations, the loop goes till i=1.
So, max is the maximum value in the subarray A[1,n].
This is a proper loop variant.

4. At the start of each iteration i of the for loop, max is the maximum value in the subarray A[1,i].
By replacing value of i, it becomes A[1,n-1], so for loop tries to find max in the array till n-1th element. As we have initialized value of max to A[n]. The above code is trying to find max element in all poaitions of array including nth element.
So, it is a proper for loop variant.

5. At the start of each iteration i of the for loop, max is the maximum value in the subarray A[i+1,n].
By replacing value of i, it becomes A[n,n], which is invalid.
So, it is not a valid for loop variant.

I hope it helped you. If so, please upvote my answer.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.