ITPEC FE Subject B April 2025 Question 13

Topic: Array Manipulation

From the answer group below, select the correct combination of answers to be inserted into A and B in the program. Here, the array index starts at 1.

The procedure maximumSubarray calculates the maximum sum of the subarray of the array T (the number of elements ≥ 1). A subarray is a contiguous portion of the array, for instance, from T[1] to T[3]. It can be as short as one element or as long as the entire array. The procedure finds one of the subarrays with the largest sum of values, and outputs the sum, the first, and the last indices of the subarray. For instance, if the content of the array is {-2, 1, -3, 4, -1, 2, 1, -5, 4}, the output will be 6, 4, and 7 representing the sum, first index, and last index, respectively. Here, the subarray from T[4] to T[7] is {4, -1, 2, 1}.

[Program]
○ maximumSubarray(integer []: T)
integer: n ← the number of elements in T
integer: i, j
integer: first, last /* the first and last indices of the subarray */
integer: sum
integer: max ← T[1] - 1
for (increase i from 1 to n by 1)
sum ← 0
for (increase j from A to n by 1)
sum ← sum + T[j]
if (sum > max)
first ← i
last ← B
max ← sum
endif
endfor
endfor
output max, first, last

Answer group

OptionAB

Explanation

A: i and B: j — the outer loop fixes the first index i and the inner loop extends the last index j from i, so sum is always the sum of the subarray from T[i] to T[j].

sum is reset to 0 for each i, then T[j] is added for j = i, i + 1, …, n. After each addition sum is the total of T[i] through T[j], so when it beats max that subarray is recorded as first ← i, last ← j. Every pair with i ≤ j is tried, single elements included (j = i), and max starts at T[1] - 1 so the first sum always replaces it.

On {-2, 1, -3, 4, -1, 2, 1, -5, 4} the best sum found for i = 1, 2, 3 is 4. At i = 4 the sums are 4, 3, 5, 6 for j = 4 to 7, and 6 is never exceeded afterwards, so the output is 6, 4, 7.

Answer (c)

Why not others:

  • •(a) and (b) — A = 1 restarts every inner loop at T[1], so sum is only ever a prefix sum while first is set to i; on the example the largest value found is 2, with first index 1
  • •(e) and (f) — A = i + 1 leaves T[i] out of the sum while still recording first ← i; on the example the sum 6 of T[4] to T[7] is found at i = 3, so the first index comes out as 3
  • •(b), (d) and (f) — B = j - 1 records the index before the element just added, so the example would report 6, 4, 6, a subarray whose sum is 5

Key rule: To enumerate every contiguous subarray, start the inner loop at the outer index and keep a running sum; the current pair (i, j) is exactly the subarray that sum describes.

Array Manipulation · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.