How do you solve Sherlock and Cost using the Two-State Rolling DP (Optimal) approach?

When to use it: The answer they want. Phrase it as 'carry high and low forward, each transitioned from both previous states'. Convert the memoized recursion into a forward sweep with two rolling values. **State.** After processing index `i`, let `high` = the maximum cost of a valid prefix ending with `B[i] = A[i]`, and `low` = the maximum cost ending with `B[i] = 1`. These two numbers summarise everything the future needs to know about the past, because the next difference depends only on the current chosen value. **Transition.** Moving to index `i`, the previous element was either at its high (`A[i-1]`) or low (`1`): - New high (choose `B[i] = A[i]`): `max(high + |A[i] − A[i-1]|, low + |A[i] − 1|)`. - New low (choose `B[i] = 1`): `max(high + |1 − A[i-1]|, low + |1 − 1|)` = `max(high + |1 − A[i-1]|, low)`. Each new state takes the better of coming from the previous high or previous low — that's why we keep both, not just the running best. **Initialisation.** At index 0 there is no previous element, so both `high` and `low` start at `0`; the first transition adds the first real difference. **Answer.** After the loop, the optimal cost is `max(high, low)` — the last element may end at either extreme. **Why O(1) space.** The recurrence reaches back exactly one index, so two scalars replace any array. No recursion means no stack-depth risk at `n = 10⁵`. Use a `long` accumulator: with `A[i]` up to `10⁹` and `n` up to `10⁵`, the sum can exceed 32-bit range. Time complexity: O(n). Space complexity: O(1).

Loading…

mediumDynamic ProgrammingSometimes asked

Sherlock and Cost

Q: How do you solve Sherlock and Cost using the Brute Force — Recurse over the Two Extremes approach?

When to use it: State it to justify the extremes-only reduction and expose the overlapping subproblems. Lean on the extremes-only insight: every `B[i]` is either `1` or `A[i]`. The brute force enumerates all `2ⁿ` such assignments by recursion. **The recursion.** Define `f(i, prev)` = the best cost achievable from index `i` onward, given the previous element was set to `prev`. At index `i` we try both choices `v ∈ {1, A[i]}`, pay `|v − prev|`, and recurse: `f(i, prev) = max over v of ( |v − prev| + f(i+1, v) )`. The base case `f(n, prev) = 0`. **Why endpoints only.** For a fixed `prev`, the contribution `|v − prev|` is maximized at one of the endpoints of `[1, A[i]]`. The next term also depends on `v`, but it too is a sum of absolute values, which is convex in `v` — and a convex function on an interval attains its maximum at an endpoint. By induction the whole tail is convex in `v`, so testing `1` and `A[i]` suffices. This is the crucial argument that shrinks an infinite range to two values. **Why we don't ship it.** Branching two ways per index gives `2ⁿ` paths — hopeless at `n = 10⁵`. But `f(i, prev)` only ever sees `prev ∈ {1, A[i-1]}`, so there are just `2n` distinct subproblems, each recomputed exponentially often. Cache them (or carry two rolling values) and the cost drops to `O(n)`. Time complexity: O(2ⁿ). Space complexity: O(n).

Dynamic Programming · 38 of 44 · 11 min

You are given an array A of n integers. Construct an array B of the same length where each element satisfies 1 ≤ B[i] ≤ A[i].

Define the cost as:

S = Σ |B[i] − B[i−1]| for i from 1 to n−1.

Return the maximum possible value of S over all valid arrays B.

In plain English

You're free to pick each B[i] anywhere from 1 up to A[i], and you want consecutive picks to be as far apart as possible. Intuitively, to make neighbours far apart you push each one to an extreme — the smallest (1) or the largest (A[i]) it's allowed to be. The only decision left at each position is which extreme, and that decision interacts only with the immediately previous one.

Examples

Example 1

Input: A = [1, 2, 3]
Output: 2
Note: Best B = [1, 1, 3] or [1, 2, 3]? B=[1,1,3] gives |1-1|+|3-1| = 0+2 = 2; B=[1,2,3] gives 1+1=2. Maximum cost is 2.

Example 2

Input: A = [10, 1, 10, 1, 10]
Output: 36
Note: Take B = [10, 1, 10, 1, 10]: differences 9+9+9+9 = 36. The forced 1s create large swings against the 10s.

Example 3

Input: A = [1, 1, 1, 5]
Output: 4
Note: First three are forced to 1; last can be up to 5. B = [1,1,1,5] gives 0+0+4 = 4.

Constraints

1 ≤ n ≤ 10⁵ (per test case)
1 ≤ A[i] ≤ 10⁹
Each B[i] is an integer with 1 ≤ B[i] ≤ A[i]
Cost is the sum of absolute differences of consecutive B values

Clarifying questions4First question: Why is B[i] always best at 1 or A[i], never in between?Explore questions

Q1.Why is B[i] always best at 1 or A[i], never in between?
The cost is a sum of absolute-value terms, and |x| is convex. For a fixed neighbour, moving B[i] toward an endpoint never decreases the contribution — at least one endpoint is at least as good as any interior point. With two neighbours, the optimum is still attained at an endpoint. So we only ever consider 1 and A[i].
Q2.Do we need to reconstruct B, or just the maximum cost?
Just the maximum cost here. The two-state DP yields the value; recovering B would need to remember the choices.
Q3.What happens when A[i] = 1?
Then B[i] must be 1 — high and low coincide. The recurrence still works because choosing A[i]=1 and choosing 1 are the same.
Q4.Could the answer be 0?
Yes — if n = 1 there are no differences, or if every A[i] = 1 the only B is all-ones with cost 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Given array A, build B with 1 ≤ B[i] ≤ A[i] maximizing Σ|B[i] − B[i−1]|. The key observation: to maximize a sum of absolute differences, every B[i] should sit at one of its two extremes — either 1 or A[i] — never in between. So track two running DP values: high[i] = best total when B[i] = A[i], and low[i] = best total when B[i] = 1. Transition each from the previous high/low by adding the absolute gap. Answer = max(high[n−1], low[n−1]). O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you prove that B[i] only ever needs to be 1 or A[i] (the extremes), then model the two choices as a two-state DP carrying high/low forward.

Where candidates slip

Trying intermediate values of B[i], or carrying only one state (forgetting the previous element could have been at the other extreme), which loses optimal transitions.

How to stand out

Justify the extremes-only claim via convexity of |x|, then collapse the O(n) two-state DP to two scalars and note A[i]=1 as the degenerate case.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recurse over the Two Extremes	`O(2ⁿ)`	`O(n)`	State it to justify the extremes-only reduction and expose the overlapping subproblems.	Read
2	Two-State Rolling DP (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'carry high and low forward, each transitioned from both previous states'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewB[i] ∈ [1, A[i]]Maximize Σ|differences|?YesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recurse over the Two Extremes

TimeO(2ⁿ)SpaceO(n)

State it to justify the extremes-only reduction and expose the overlapping subproblems.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First argue you only ever set B[i] to 1 or A[i]. Then the search is: for each index, pick one of two values.

2Hint 2Explore hint

Recurse carrying the value chosen for the previous element. At index i, try B[i]=1 and B[i]=A[i], add |B[i] − prev|, and recurse.

3Hint 3Explore hint

That's 2 branches per index → 2ⁿ paths, but the state is just (index, previous choice ∈ {1, A[i-1]}) — only 2n distinct states.

A · Core idea

Lean on the extremes-only insight: every B[i] is either 1 or A[i]. The brute force enumerates all 2ⁿ such assignments by recursion.

The recursion. Define f(i, prev) = the best cost achievable from index i onward, given the previous element was set to prev. At index i we try both choices v ∈ {1, A[i]}, pay |v − prev|, and recurse: f(i, prev) = max over v of ( |v − prev| + f(i+1, v) ). The base case f(n, prev) = 0.

Why endpoints only. For a fixed prev, the contribution |v − prev| is maximized at one of the endpoints of [1, A[i]]. The next term also depends on v, but it too is a sum of absolute values, which is convex in v — and a convex function on an interval attains its maximum at an endpoint. By induction the whole tail is convex in v, so testing 1 and A[i] suffices. This is the crucial argument that shrinks an infinite range to two values.

Why we don't ship it. Branching two ways per index gives 2ⁿ paths — hopeless at n = 10⁵. But f(i, prev) only ever sees prev ∈ {1, A[i-1]}, so there are just 2n distinct subproblems, each recomputed exponentially often. Cache them (or carry two rolling values) and the cost drops to O(n).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [1, 2, 3]

Interactive diagram

Binary choice tree over extremes

B[0]

Active call / nodeSupporting contextReturned stateNot active

Each level picks 1 or A[i]; identical (i, prev) states recur — the memoization target.

Final result2

C · Code with teaching comments

Reference implementation previewpublic long cost(int[] A) { return f(A, 1, A.length > 0 ? A[0] : 1, A.length > 0 ? 1 : 1, 0); } // recurse with the two possible previous values explicitlyExplore the full code

solution.javaJava

Brute Force — Recurse over the Two Extremes — reference

3 teaching notes

1
public long cost(int[] A) {
2
    return f(A, 1, A.length > 0 ? A[0] : 1, A.length > 0 ? 1 : 1, 0);
3
}
4
 
5
// recurse with the two possible previous values explicitly
6
private long f(int[] A, int i, long prevHigh, long prevLow, long acc) {
7
    // Past the last element — no more differences to add.
8
    if (i == A.length) return acc;
9
    // previous was A[i-1] (high) or 1 (low); try both current extremes
10
    long takeHighFromHigh = f(A, i + 1, A[i], 1, acc); // placeholder structure
11
    return 0; // see memoized version below for the clean formulation
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

The infinite range [1, A[i]] collapses to two candidates because the cost is convex in each B[i], and convex functions peak at endpoints. That single observation is what makes the problem a finite two-state DP instead of an optimization over reals.

ComplexityO(2ⁿ) time, O(n) space — Two branches at each of n indices form a binary tree of 2ⁿ leaves; recursion depth O(n).

E · Edge cases and pitfalls3Trying interior values of B[i] — unnecessary and exponentially slower.Explore edge cases

Pitfalls

Trying interior values of B[i] — unnecessary and exponentially slower.
Forgetting to seed both choices for B[0].
Running unmemoized at large n — 2ⁿ never returns.

03.2

Approach 2 of 2 · Optimal

Two-State Rolling DP (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'carry high and low forward, each transitioned from both previous states'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define high = best total when the current B is A[i], low = best total when the current B is 1.

2Hint 2Explore hint

To extend to index i, the previous element could have been high (value A[i-1]) or low (value 1). Try both and keep the max.

3Hint 3Explore hint

new_high = max(high + |A[i]-A[i-1]|, low + |A[i]-1|); new_low = max(high + |1-A[i-1]|, low + 0). Answer = max(high, low).

A · Core idea

Convert the memoized recursion into a forward sweep with two rolling values.

State. After processing index i, let high = the maximum cost of a valid prefix ending with B[i] = A[i], and low = the maximum cost ending with B[i] = 1. These two numbers summarise everything the future needs to know about the past, because the next difference depends only on the current chosen value.

Transition. Moving to index i, the previous element was either at its high (A[i-1]) or low (1):

New high (choose B[i] = A[i]): max(high + |A[i] − A[i-1]|, low + |A[i] − 1|).
New low (choose B[i] = 1): max(high + |1 − A[i-1]|, low + |1 − 1|) = max(high + |1 − A[i-1]|, low).

Each new state takes the better of coming from the previous high or previous low — that's why we keep both, not just the running best.

Initialisation. At index 0 there is no previous element, so both high and low start at 0; the first transition adds the first real difference.

Answer. After the loop, the optimal cost is max(high, low) — the last element may end at either extreme.

Why O(1) space. The recurrence reaches back exactly one index, so two scalars replace any array. No recursion means no stack-depth risk at n = 10⁵. Use a long accumulator: with A[i] up to 10⁹ and n up to 10⁵, the sum can exceed 32-bit range.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [10, 1, 10, 1, 10]

Two states transitioning each step

How to read it:Each new state is fed by both previous states; the max keeps the better path.

Rendering diagram…

Final result36

C · Code with teaching comments

solution.javaJava

Two-State Rolling DP (Optimal) — optimal

4 teaching notes

1
public long cost(int[] A) {
2
    int n = A.length;
3
    // Zero or one element → no differences → cost 0.
4
    if (n <= 1) return 0;
5
    long high = 0, low = 0;
6
    for (int i = 1; i < n; i++) {
7
        long nh = Math.max(high + Math.abs((long) A[i] - A[i - 1]),
8
                           low  + Math.abs((long) A[i] - 1));
9
        long nl = Math.max(high + Math.abs(1L - A[i - 1]),
10
                           low  + 0);
11
        high = nh;
12
        low = nl;
13
    }
14
    // Last element may end at either extreme — take the larger.
15
    return Math.max(high, low);
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The reason two states beat one running maximum: the best continuation from index i depends on which extreme the previous element took, not just on the previous best cost. Carrying high and low separately preserves exactly that dependency — a hallmark of state-machine DP.

ComplexityO(n) time, O(1) space — One pass over n elements, O(1) work per step (two max computations) → O(n) time. Only two scalars retained → O(1) space.

E · Edge cases and pitfalls7A = [1, 2, 3] — i=1: high=1,low=0; i=2: high=max(1+1,0+2)=2, low=max(1+1,0)=2 → max 2.Explore edge cases

Edge cases handled

A = [1, 2, 3]i=1: high=1,low=0; i=2: high=max(1+1,0+2)=2, low=max(1+1,0)=2 → max 2.
A = [1]n=1 → returns 0 (no differences).
A = [5, 5, 5]Best swings 5↔1: B=[5,1,5] or [1,5,1] → 4+4=8.
A = [1, 1, 1, 5]First three forced to 1 (high=low until A grows); last adds |5-1|=4 → 4.

Pitfalls

Carrying only one running max instead of separate high/low — loses transitions from the other extreme.
Using int accumulators — overflow when A[i]·n exceeds 2³¹; use long.
Forgetting the n ≤ 1 guard, which would index A[i-1] out of range.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long cost(int[] A) { int n = A.length; if (n <= 1) return 0; long high = 0, low = 0; for (int i = 1; i < n; i++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Trying interior values of B[i]

The cost is convex in each B[i], so the maximum is always at an endpoint. Searching interior values is both unnecessary and prevents an O(n) solution.

Explore the code comparison

Don't write this

for v in range(1, A[i] + 1):   # entire range
    best = max(best, abs(v - prev) + ...)

Write this instead

for v in (1, A[i]):            # only the two extremes
    best = max(best, abs(v - prev) + ...)

Collapsing to one state

The next difference depends on which extreme the previous element took. Keeping a single 'best so far' discards the value needed to compute the next gap.

Explore the code comparison

Don't write this

long best = ...;
best = Math.max(best + |A[i]-A[i-1]|, ...);  // ambiguous: which prev value?

Write this instead

long nh = Math.max(high + |A[i]-A[i-1]|, low + |A[i]-1|);
long nl = Math.max(high + |1-A[i-1]|, low);

Integer overflow

With A[i] up to 10⁹ and n up to 10⁵, the total cost can reach ~10¹⁴ — far beyond 32-bit int.

Explore the code comparison

Don't write this

int high = 0, low = 0;  // overflows

Write this instead

long high = 0, low = 0;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-state (high/low) DP — each element pinned to an extreme

Code pattern to memorize

high = low = 0   # high: B[i]=A[i], low: B[i]=1
for i in 1..n-1:
    nh = max(high + |A[i] - A[i-1]|, low + |A[i] - 1|)
    nl = max(high + |1 - A[i-1]|,   low + |1 - 1|)
    high, low = nh, nl
answer = max(high, low)

Rules to remember

1To maximize a sum of absolute differences, each B[i] is best at an endpoint of its range: 1 or A[i]. Interior values can never beat both extremes simultaneously.
2Keep exactly two states per index — high (chose A[i]) and low (chose 1) — because the next element's gain depends only on the previous element's chosen value.
3Each transition tries both previous choices and keeps the max: the previous element could have been high or low.
4Initialise high = low = 0 at index 0 — there's no earlier element, so the first |difference| term is 0 either way.
5When A[i] == 1, high and low collapse to the same value (the only choice is 1); the recurrence handles this automatically.

Use this pattern when

Maximize/minimize a sum of |adjacent differences| with per-element value ranges
Each position has a small fixed set of optimal candidate values (here, two extremes)
A linear chain where the next term's contribution depends only on the previous choice
State-machine DP with a constant number of states per index

Choose another pattern when

Minimizing the sum of differences → the optimum is the opposite (cluster values), different reasoning
Differences are squared or weighted nonlinearly → endpoints may not be optimal; reconsider
Values are continuous with no integer constraint → still endpoints, but framing differs
Dependencies reach back more than one element → more states or a different model

Interview takeaway

When you're maximizing a sum of absolute differences and each term is bounded, the extremes win — so the continuous range [1, A[i]] collapses to just {1, A[i]}. That reduction turns an infinite choice space into a clean two-state DP solvable in O(1) space.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTwo-state (high/low) state-machine DP. When maximizing a sum of absolute differences with per-element ranges, convexity pins each value to an extreme, leaving two states per index. Carry both forward — same skeleton as Best Time to Buy/Sell with Cooldown and Wiggle Subsequence.

Practice queueDirect variations and pattern siblings

Direct follow-ups

House Robber
Another two-choice linear DP — take/skip instead of high/low.
Best Time to Buy and Sell Stock with Cooldown
Coming soon
State-machine DP with a few states per index — same carry-both-states idea.
Wiggle Subsequence
Coming soon
Up/down two-state DP maximizing alternation — sibling of high/low here.
Max Array Sum
Non-adjacent selection DP — another bounded-look-back linear recurrence.

Same pattern

←

Sam and Substrings

Continue · Next problem

Common Child

mediumDynamic ProgrammingSometimes asked

Sherlock and Cost

Dynamic Programming · 38 of 44 · 11 min

You are given an array A of n integers. Construct an array B of the same length where each element satisfies 1 ≤ B[i] ≤ A[i].

Define the cost as:

S = Σ |B[i] − B[i−1]| for i from 1 to n−1.

Return the maximum possible value of S over all valid arrays B.

In plain English

Examples

Example 1

Input: A = [1, 2, 3]
Output: 2
Note: Best B = [1, 1, 3] or [1, 2, 3]? B=[1,1,3] gives |1-1|+|3-1| = 0+2 = 2; B=[1,2,3] gives 1+1=2. Maximum cost is 2.

Example 2

Input: A = [10, 1, 10, 1, 10]
Output: 36
Note: Take B = [10, 1, 10, 1, 10]: differences 9+9+9+9 = 36. The forced 1s create large swings against the 10s.

Example 3

Input: A = [1, 1, 1, 5]
Output: 4
Note: First three are forced to 1; last can be up to 5. B = [1,1,1,5] gives 0+0+4 = 4.

Constraints

1 ≤ n ≤ 10⁵ (per test case)
1 ≤ A[i] ≤ 10⁹
Each B[i] is an integer with 1 ≤ B[i] ≤ A[i]
Cost is the sum of absolute differences of consecutive B values

Clarifying questions4First question: Why is B[i] always best at 1 or A[i], never in between?Explore questions

Q1.Why is B[i] always best at 1 or A[i], never in between?
The cost is a sum of absolute-value terms, and |x| is convex. For a fixed neighbour, moving B[i] toward an endpoint never decreases the contribution — at least one endpoint is at least as good as any interior point. With two neighbours, the optimum is still attained at an endpoint. So we only ever consider 1 and A[i].
Q2.Do we need to reconstruct B, or just the maximum cost?
Just the maximum cost here. The two-state DP yields the value; recovering B would need to remember the choices.
Q3.What happens when A[i] = 1?
Then B[i] must be 1 — high and low coincide. The recurrence still works because choosing A[i]=1 and choosing 1 are the same.
Q4.Could the answer be 0?
Yes — if n = 1 there are no differences, or if every A[i] = 1 the only B is all-ones with cost 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you prove that B[i] only ever needs to be 1 or A[i] (the extremes), then model the two choices as a two-state DP carrying high/low forward.

Where candidates slip

Trying intermediate values of B[i], or carrying only one state (forgetting the previous element could have been at the other extreme), which loses optimal transitions.

How to stand out

Justify the extremes-only claim via convexity of |x|, then collapse the O(n) two-state DP to two scalars and note A[i]=1 as the degenerate case.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recurse over the Two Extremes	`O(2ⁿ)`	`O(n)`	State it to justify the extremes-only reduction and expose the overlapping subproblems.	Read
2	Two-State Rolling DP (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'carry high and low forward, each transitioned from both previous states'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recurse over the Two Extremes

TimeO(2ⁿ)SpaceO(n)

State it to justify the extremes-only reduction and expose the overlapping subproblems.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First argue you only ever set B[i] to 1 or A[i]. Then the search is: for each index, pick one of two values.

2Hint 2Explore hint

Recurse carrying the value chosen for the previous element. At index i, try B[i]=1 and B[i]=A[i], add |B[i] − prev|, and recurse.

3Hint 3Explore hint

That's 2 branches per index → 2ⁿ paths, but the state is just (index, previous choice ∈ {1, A[i-1]}) — only 2n distinct states.

A · Core idea

Lean on the extremes-only insight: every B[i] is either 1 or A[i]. The brute force enumerates all 2ⁿ such assignments by recursion.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [1, 2, 3]

Interactive diagram

Binary choice tree over extremes

B[0]

Active call / nodeSupporting contextReturned stateNot active

Each level picks 1 or A[i]; identical (i, prev) states recur — the memoization target.

Final result2

C · Code with teaching comments

solution.javaJava

Brute Force — Recurse over the Two Extremes — reference

3 teaching notes

1
public long cost(int[] A) {
2
    return f(A, 1, A.length > 0 ? A[0] : 1, A.length > 0 ? 1 : 1, 0);
3
}
4
 
5
// recurse with the two possible previous values explicitly
6
private long f(int[] A, int i, long prevHigh, long prevLow, long acc) {
7
    // Past the last element — no more differences to add.
8
    if (i == A.length) return acc;
9
    // previous was A[i-1] (high) or 1 (low); try both current extremes
10
    long takeHighFromHigh = f(A, i + 1, A[i], 1, acc); // placeholder structure
11
    return 0; // see memoized version below for the clean formulation
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(2ⁿ) time, O(n) space — Two branches at each of n indices form a binary tree of 2ⁿ leaves; recursion depth O(n).

E · Edge cases and pitfalls3Trying interior values of B[i] — unnecessary and exponentially slower.Explore edge cases

Pitfalls

Trying interior values of B[i] — unnecessary and exponentially slower.
Forgetting to seed both choices for B[0].
Running unmemoized at large n — 2ⁿ never returns.

03.2

Approach 2 of 2 · Optimal

Two-State Rolling DP (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'carry high and low forward, each transitioned from both previous states'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define high = best total when the current B is A[i], low = best total when the current B is 1.

2Hint 2Explore hint

To extend to index i, the previous element could have been high (value A[i-1]) or low (value 1). Try both and keep the max.

3Hint 3Explore hint

new_high = max(high + |A[i]-A[i-1]|, low + |A[i]-1|); new_low = max(high + |1-A[i-1]|, low + 0). Answer = max(high, low).

A · Core idea

Convert the memoized recursion into a forward sweep with two rolling values.

Transition. Moving to index i, the previous element was either at its high (A[i-1]) or low (1):

New high (choose B[i] = A[i]): max(high + |A[i] − A[i-1]|, low + |A[i] − 1|).
New low (choose B[i] = 1): max(high + |1 − A[i-1]|, low + |1 − 1|) = max(high + |1 − A[i-1]|, low).

Each new state takes the better of coming from the previous high or previous low — that's why we keep both, not just the running best.

Initialisation. At index 0 there is no previous element, so both high and low start at 0; the first transition adds the first real difference.

Answer. After the loop, the optimal cost is max(high, low) — the last element may end at either extreme.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [10, 1, 10, 1, 10]

Two states transitioning each step

How to read it:Each new state is fed by both previous states; the max keeps the better path.

Rendering diagram…

Final result36

C · Code with teaching comments

solution.javaJava

Two-State Rolling DP (Optimal) — optimal

4 teaching notes

1
public long cost(int[] A) {
2
    int n = A.length;
3
    // Zero or one element → no differences → cost 0.
4
    if (n <= 1) return 0;
5
    long high = 0, low = 0;
6
    for (int i = 1; i < n; i++) {
7
        long nh = Math.max(high + Math.abs((long) A[i] - A[i - 1]),
8
                           low  + Math.abs((long) A[i] - 1));
9
        long nl = Math.max(high + Math.abs(1L - A[i - 1]),
10
                           low  + 0);
11
        high = nh;
12
        low = nl;
13
    }
14
    // Last element may end at either extreme — take the larger.
15
    return Math.max(high, low);
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — One pass over n elements, O(1) work per step (two max computations) → O(n) time. Only two scalars retained → O(1) space.

E · Edge cases and pitfalls7A = [1, 2, 3] — i=1: high=1,low=0; i=2: high=max(1+1,0+2)=2, low=max(1+1,0)=2 → max 2.Explore edge cases

Edge cases handled

A = [1, 2, 3]i=1: high=1,low=0; i=2: high=max(1+1,0+2)=2, low=max(1+1,0)=2 → max 2.
A = [1]n=1 → returns 0 (no differences).
A = [5, 5, 5]Best swings 5↔1: B=[5,1,5] or [1,5,1] → 4+4=8.
A = [1, 1, 1, 5]First three forced to 1 (high=low until A grows); last adds |5-1|=4 → 4.

Pitfalls

Carrying only one running max instead of separate high/low — loses transitions from the other extreme.
Using int accumulators — overflow when A[i]·n exceeds 2³¹; use long.
Forgetting the n ≤ 1 guard, which would index A[i-1] out of range.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long cost(int[] A) { int n = A.length; if (n <= 1) return 0; long high = 0, low = 0; for (int i = 1; i < n; i++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Trying interior values of B[i]

The cost is convex in each B[i], so the maximum is always at an endpoint. Searching interior values is both unnecessary and prevents an O(n) solution.

Explore the code comparison

Don't write this

for v in range(1, A[i] + 1):   # entire range
    best = max(best, abs(v - prev) + ...)

Write this instead

for v in (1, A[i]):            # only the two extremes
    best = max(best, abs(v - prev) + ...)

Collapsing to one state

The next difference depends on which extreme the previous element took. Keeping a single 'best so far' discards the value needed to compute the next gap.

Explore the code comparison

Don't write this

long best = ...;
best = Math.max(best + |A[i]-A[i-1]|, ...);  // ambiguous: which prev value?

Write this instead

long nh = Math.max(high + |A[i]-A[i-1]|, low + |A[i]-1|);
long nl = Math.max(high + |1-A[i-1]|, low);

Integer overflow

With A[i] up to 10⁹ and n up to 10⁵, the total cost can reach ~10¹⁴ — far beyond 32-bit int.

Explore the code comparison

Don't write this

int high = 0, low = 0;  // overflows

Write this instead

long high = 0, low = 0;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-state (high/low) DP — each element pinned to an extreme

Code pattern to memorize

high = low = 0   # high: B[i]=A[i], low: B[i]=1
for i in 1..n-1:
    nh = max(high + |A[i] - A[i-1]|, low + |A[i] - 1|)
    nl = max(high + |1 - A[i-1]|,   low + |1 - 1|)
    high, low = nh, nl
answer = max(high, low)

Rules to remember

1To maximize a sum of absolute differences, each B[i] is best at an endpoint of its range: 1 or A[i]. Interior values can never beat both extremes simultaneously.
2Keep exactly two states per index — high (chose A[i]) and low (chose 1) — because the next element's gain depends only on the previous element's chosen value.
3Each transition tries both previous choices and keeps the max: the previous element could have been high or low.
4Initialise high = low = 0 at index 0 — there's no earlier element, so the first |difference| term is 0 either way.
5When A[i] == 1, high and low collapse to the same value (the only choice is 1); the recurrence handles this automatically.

Use this pattern when

Maximize/minimize a sum of |adjacent differences| with per-element value ranges
Each position has a small fixed set of optimal candidate values (here, two extremes)
A linear chain where the next term's contribution depends only on the previous choice
State-machine DP with a constant number of states per index

Choose another pattern when

Minimizing the sum of differences → the optimum is the opposite (cluster values), different reasoning
Differences are squared or weighted nonlinearly → endpoints may not be optimal; reconsider
Values are continuous with no integer constraint → still endpoints, but framing differs
Dependencies reach back more than one element → more states or a different model

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

House Robber
Another two-choice linear DP — take/skip instead of high/low.
Best Time to Buy and Sell Stock with Cooldown
Coming soon
State-machine DP with a few states per index — same carry-both-states idea.
Wiggle Subsequence
Coming soon
Up/down two-state DP maximizing alternation — sibling of high/low here.
Max Array Sum
Non-adjacent selection DP — another bounded-look-back linear recurrence.

Same pattern

←

Sam and Substrings

Continue · Next problem

Common Child