1D DP (Including Kadane) — Reasoning Check

Apply the module invariants, traces, and boundary conditions.

Get every question correct to pass this checkpoint. You can review feedback, revise your answers, and submit again.

1. Houses form a circle with values [6,1,2,7]. What is the maximum obtainable value without selecting adjacent houses, including across the circular boundary? Enter one integer.

2. A MaximumSubarray implementation initializes its global answer to zero and returns 0 for [-8,-3,-5]. What contract did it violate?

Select one answer.

The array must be sorted first; sorting would make the maximum sum zero. The subarray must be nonempty; the correct answer is -3, so zero is not a valid initial best candidate. Negative values must be ignored entirely, leaving the empty array as the required output. The answer must be the sum of the whole array, which is -16.

3. Maximum-product DP has processed [-2,-3], with maximum ending product 6 and minimum ending product -3. After reading -4, what are the new maximum and minimum ending products?

Select one answer.

Maximum 12 and minimum -24. Maximum -4 and minimum -24. Maximum 24 and minimum -12. Maximum 12 and minimum -4.

4. Consider WordBreak("bedbath", ["bed","be","dbath"]) and CoinChange([1,4,6], amount=8). What are the correct results, despite choosing the longest initial word or largest available coin greedily?

Select one answer.

Word Break is true, and the minimum coin count is 2. Word Break is false, and the minimum coin count is 3. Word Break is true, and the minimum coin count is 3. Word Break is false, and the minimum coin count is 2.

5. For the strictly increasing subsequence problem on [4,2,2,3,1,5], how should a tails-based algorithm handle the second 2, and what final length should it report?

Select one answer.

Replace the first tail >2; the final length is 4. Discard every duplicate value and return the number of distinct values, which is 5. Always append a value equal to the current tail; the final length is 4. Replace the first tail >=2; the final length is 3.

6. With digit codes 1 through 26 and no standalone zero, how many decodings does "11106" have? Enter one integer.

Auto-advance on pass

Join Discord