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].