Maximization Problems with DP

Symmetric to minimization: use -inf sentinels, max transitions, and prove greedy fails before jumping to DP.

Why this shows up in the real world

Revenue stacking non-overlapping jobs. Game score maximization.

Core idea (explained for students)

dp[i]=max over choices with careful indexing on previous states.

Try this in Python

def max_rob_linear(houses: list[int]) -> int:
    incl, excl = 0, 0
    for x in houses:
        new_incl = excl + x
        new_excl = max(incl, excl)
        incl, excl = new_incl, new_excl
    return max(incl, excl)


print(max_rob_linear([2, 7, 9, 3, 1]))

Common mistakes

• Initializing with 0 when negatives allowed—max picks spurious zero.
• Integer overflow adding large positives.

Key takeaways

• Mirror min DP checklist with signs flipped.