Why doesn't the longest increasing run of daily active users equal the longest increasing subsequence?
answer
- contiguity is an extra constraint
- gaps allowed, reordering not
- one pass finds runs, not subsequences
- define the best ending exactly at each day
- then take a maximum over all days
basics
~20 sA run must be contiguous; a subsequence only keeps the original order and may skip days. So the longest run is a lower bound on the longest increasing subsequence — one pass finds it, while the subsequence needs a dynamic program.
solid answer
~50 sA run is contiguous — consecutive days, no gaps — so one pass with a counter that resets on every drop finds the longest increasing run in O(n) time and O(1) space. A subsequence only has to preserve order; it may skip arbitrarily many days, so a single dip no longer ends the candidate. The longest run is therefore a lower bound, often a strict one: on the daily counts 3, 1, 4, 1, 5, 9, 2, 6 the longest run is 3 (1, 5, 9) while the longest increasing subsequence is 4 (1, 4, 5, 9). The standard quadratic dynamic program defines `len[i]` as the length of the longest increasing subsequence *ending exactly at day i*, sets it to `1 + max(len[j])` over all earlier days `j` with a smaller count, and takes the maximum over all `i` — O(n^2) time, O(n) space.
code
pseudocode · 10 lines// dau: daily active-user counts, n >= 1
answer = 1
for i in 0..n-1
len[i] = 1
for j in 0..i-1
if dau[j] < dau[i] and len[j] + 1 > len[i]
len[i] = len[j] + 1
if len[i] > answer
answer = len[i]
return answergo deeper
Be ready to say plainly that a run needs consecutive days while a subsequence may skip days but never reorder them, and to give one short history where the two answers differ.
Explain the state as best-ending-exactly-at-index, justify why a prefix-wide state cannot be extended, and derive the quadratic cost from the backwards scan. Remember the final maximum over all indices.
Bring the specification question first: strictly increasing or non-decreasing, length only or the actual days. Then size the input and say at what n the quadratic version stops being acceptable.
Own the choice between an easily-modified quadratic recurrence and a faster method that is harder to extend and to reconstruct from. Be able to argue which one a team should carry given how often the definition of the metric changes.
## Two different questions about the same history A leaderboard records daily active users, one count per day. "How long did the numbers climb?" has two reasonable readings, and interviews exploit the gap between them. - **Longest increasing run** — the longest block of *consecutive* days on which the count strictly rose. Contiguity is required. - **Longest increasing subsequence (LIS)** — the longest set of days, in their original order, whose counts strictly rise. Days may be skipped freely; only order is preserved. Every run is a subsequence, so the longest run is always at most the LIS. It is frequently much shorter: the counts `3, 1, 4, 1, 5, 9, 2, 6` have a longest run of 3 (`1, 5, 9`) and an LIS of 4 (`1, 4, 5, 9`, or `1, 4, 5, 6`). The two coincide only when the optimal subsequence happens to be contiguous. The misconception worth naming explicitly: *a subsequence is not a substring, and it is not a re-ordering either.* Skipping is allowed; rearranging is not. A candidate who answers 8 for the LIS above has quietly turned the question into "sort it and count". ## The run: one pass Walk the days, keep a current length starting at 1, increment it whenever today's count exceeds yesterday's, reset it to 1 otherwise, and track the maximum. O(n) time, O(1) space, nothing to memoize. The reset is what makes it easy — and what makes it the wrong tool for the subsequence question, since it throws away everything before a dip. ## The subsequence: state, transition, cost The dynamic program hinges on choosing the right state. Define: > `len[i]` = the length of the longest strictly increasing subsequence **ending exactly at day i**. The phrase "ending exactly at" is load-bearing. The tempting alternative — "the longest increasing subsequence within the first `i` days" — is not extensible, because to extend a subsequence you must know the value it currently ends on, and a prefix-wide maximum has forgotten that. Anchoring the state at a specific index keeps the last value in hand. Transition: any earlier day `j < i` with `dau[j] < dau[i]` can be the predecessor, so `len[i] = 1 + max(len[j] over all j < i with dau[j] < dau[i])`, or 1 if no such `j` exists. The answer is `max(len[i])` over all `i` — **not** `len[n-1]`, because the optimal subsequence need not end on the last day. Forgetting that final maximum is one of the two most common bugs; the other is comparing indices instead of values. Cost: two nested loops, O(n^2) time and O(n) space. On a year of history (n around 365) that is trivial; on a per-user history of 10^6 points it is 10^12 operations and unusable. ## Strict versus non-strict The comparison in the inner test decides which problem you solved. `dau[j] < dau[i]` gives the longest **strictly** increasing subsequence; `dau[j] <= dau[i]` gives the longest **non-decreasing** one, which is never shorter and is usually a different answer on real data full of flat days. Ask which one is wanted; a plateau of identical counts is exactly the case where a product owner and an engineer mean different things. ## The faster route, and what it costs you There is an O(n log n) method that maintains an auxiliary `tails` array where `tails[k]` holds the smallest value that can end an increasing subsequence of length `k+1` seen so far. Each new count either extends `tails` by one, when it exceeds every entry, or replaces the first entry that is not smaller than it — a position found by a logarithmic search over `tails`, which is sorted by construction. The final length of `tails` is the LIS length. Two things about it are worth holding onto. First, it computes the **length** directly; the contents of `tails` at the end are not, in general, an actual subsequence of the input, so reconstructing the days themselves requires extra bookkeeping. Second, the quadratic version is far easier to modify: weighted variants, "longest chain under a custom comparison", or a requirement to report every optimal subsequence all sit naturally in the `len[i]` formulation and awkwardly in the `tails` one. Reach for the faster method when n is large and only the length is needed; keep the quadratic one when n is a few thousand and the recurrence has to keep changing. ## The pattern behind both Both of these are one-dimensional sequence dynamic programs: one state per index, a transition that looks backwards, a scalar answer. The run's "transition" happens to look back exactly one position, which is why it degenerates into a simple counter; the LIS looks back over all earlier positions, which is where the quadratic factor comes from. Recognizing how far back a transition must reach is a reliable way to predict the cost of a sequence DP before writing it.
- Why is the answer the maximum over all len[i] rather than len[n-1]?Because len[i] is anchored: it counts only subsequences that end exactly at day i. The optimal subsequence has no obligation to include the last day, so len[n-1] answers a narrower question. Taking the maximum over every index is what lifts the anchored states back to the global answer, and forgetting it is one of the two classic bugs in this dynamic program.
- Why not define the state as the best answer within the first i days?Because that state cannot be extended. To append day i to an earlier subsequence you must know the value that subsequence currently ends on, and a prefix-wide maximum has discarded it — two prefixes with the same best length can end on very different counts. Anchoring the state at a specific index keeps the ending value available, which is exactly what the transition needs.
- What changes if flat days should count as part of the climb?Only the comparison. Using strictly-less between the earlier and later counts computes the longest strictly increasing subsequence; using less-or-equal computes the longest non-decreasing one, which is never shorter. Real histories are full of plateaus, so this is a specification question worth asking before coding rather than a detail to guess at.
saying these in an interview costs you the question
- Says a subsequence must be contiguous
- Sorts the history and counts, treating order as irrelevant
- Returns len[n-1] instead of the maximum over all indices
- Compares day indices instead of the counts
- Claims the longest run is always the longest subsequence