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

Question

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

COMPUTE-MAX(A,n)

max = A[n]

for i = n-1 downto 1

if A[i] > 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 A[1..i]. 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[i..n]. At 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[i+1..n].

Explanation / Answer

Answer: At the start of each iteration i of the for loop, max is the maximum value in the subarray A[i+1..n].

Above option is the correct loop invariant of the for loop

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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