Micro-questions over the max slice module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The problem
1. State the problem in trading terms.
Answer
Given daily profit/loss figures, find the contiguous window of days maximising cumulative profit.
2. What is a subarray / slice?
Answer
A contiguous block of elements — a date range window on a calendar. Contiguity is what makes it a different problem from “pick any subset”.
3. Name three applications.
Answer
Optimal stock holding window; isolating the highest-amplitude segment of a noisy signal; identifying the highest-density gene region in a DNA strand.
B. The two naive approaches
4. Why is brute force ?
Answer
There are possible subarrays, and each is summed from scratch in .
5. What single change gives ?
Answer
Maintain a running sum for a fixed start p. Moving q forward extends it by one addition instead of recomputing.
6. What is the general lesson from that step?
Answer
Recomputing what you already knew is the usual source of an extra factor of — the same move that turns many cubic solutions quadratic.
C. Kadane’s algorithm
7. State the recurrence in words.
Answer
The best subarray ending at position is either the best ending at extended by one element, or a brand new subarray starting at alone.
8. State it as a rule of thumb.
Answer
If carrying the negative baggage of a prior run makes things worse than starting fresh, cut and restart.
9. What do max_ending_here and max_so_far mean?
Answer
max_ending_here = the best sum achievable by any subarray ending exactly at the current position. max_so_far = the global running maximum across all positions so far.
10. Write the loop.
Answer
max_ending_here = max_so_far = 0
for value in A:
max_ending_here = max(0, max_ending_here + value)
max_so_far = max(max_so_far, max_ending_here)11. What is the max(0, ...) doing?
Answer
Resetting to 0 allows starting a completely new subarray from the next element — equivalent to allowing the empty slice as a baseline.
12. Trace it on [-2,3,4,-1,5,-8,4,1].
Answer
max_ending_here: 0, 3, 7, 6, 11, 3, 7, 8. max_so_far: 0, 3, 7, 7, 11, 11, 11, 11. Answer 11.
13. What are its costs?
Answer
time, space — one pass, two variables.
14. What does this version return for an all-negative array, and is that right?
Answer
0 — because the empty slice is allowed. If the problem requires a non-empty subarray, initialise both to A[0] and drop the max(0, ...) clamp. Read the problem statement for which variant is wanted.
D. Why it is DP
15. What is the subproblem?
Answer
max_ending_here[i] = the best subarray sum ending at index .
16. Why must the state pin the ending index?
Answer
Because otherwise you cannot tell whether the next element can extend the best run — the same reason LIS pins its ending element.
17. Where is the optimal substructure?
Answer
The global answer is built from optimal answers to smaller problems — max_so_far is the max over all max_ending_here values.
18. Why is the space rather than ?
Answer
Only the immediately previous subproblem value is ever needed, so the table collapses to one variable.
19. Where is the global answer, and why not the last cell?
Answer
It is the maximum over all cells, not the last one — because the state pins the ending position, no single cell holds the global answer.
20. Summarise Kadane’s in one sentence.
Answer
Carry the best run ending here, drop it the moment it turns negative, and remember the best you ever saw — dynamic programming compressed into two variables.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Max Slice Algorithms — the module
- Classic 1-D DP — Question Bank — the same “pin the ending index” move
- Divide and Conquer — Question Bank — the solution this one beats
Software engineering
Infrastructure & security
Computer science
Hardware & engineering