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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Algorithms