ITPEC FE Subject B April 2025 Question 13

Brute-force maximum subarray: enumerate all subarrays by fixing start index i and extending end index j

The outer loop variable i represents the start of the current subarray. The inner loop variable j represents the end. For each i, the inner loop begins at j = i and extends to n, accumulating sum ← sum + T[j].

• •Blank A = `i`: the inner loop must start at the same position as the outer loop so that sum accumulates T[i], T[i+1], …, T[j]. Starting from 1 would mix unrelated prefix elements into the sum.
• •Blank B = `j`: when sum > max, the subarray runs from index i to index j, so last ← j. Using j - 1 would exclude the element just added.

Why not others:
- a) A=1, B=j — inner loop always starts from 1 regardless of i, producing sums of subarrays starting at index 1 only
- b) A=1, B=j-1 — same problem as (a), plus last is off by one
- d) A=i, B=j-1 — correct start but last excludes the element that triggered the new maximum
- e) A=i+1, B=j — skips T[i] itself, so the subarray never includes its own start element
- f) A=i+1, B=j-1 — both start and end are wrong

Key rule: In a brute-force subarray enumeration, the inner index starts at the outer index (j = i) and the recorded end is the current inner index (last = j), not one before or after.

AI-generated — may contain errors