Here’s an easy discrete optimization problem that many computing students see: "maximum sum subarray".
\(I\) is some finite chain, e.g. \(I=[0,n)\).
Let \(F = \{[a,b] \mid a,b\in I\}\) be the set of intervals in \(I\).
There’s a finite sequence of integers \(s\in\mathbb{Z}^{I}\).
For interval \(J \in F\), let \(f(J)=\sum_{i\in J}s(i)\).
Find \[\max_{J\in F} f(J)\]
solution via set system decomposition
Let \(F_b = \{[a,b]\mid a\in I, a\leq b\}\). \(F_b\) is the set of intervals in \(I\) whose lowest upper bound is b.
\[F = \{[a,b] \mid a,b\in I\} = \{\emptyset\}\cup\{[a,b] \mid a,b\in I,a\leq b\}=\{\emptyset\}\cup\bigcup_{b\in I}F_b\]
If \(b\) is not the maximum element of I, then let \(b + 1\) be the unique element that covers \(b\), i.e. \(b \leq c \leq b + 1\) implies that \(c=b\) or \(c=b+1\)
For \(b,b+1\in I\), \[F_{b+1}=\{J\cup \{b+1\}\mid J\in F_{b}\}\cup\{\{b+1\}\}\]
\(f\) is modular, so
\[\{f(J) \mid J\in F_{b+1}\}=\{f(J)+ f(\{b+1\}) \mid J\in F_{b}\}\cup\{f(\{b+1\})\}\]
\(f(\{b+1\})=s(b+1)\), so
\[\{f(J) \mid J\in F_{b+1}\}=\{f(J)+ s(b+1) \mid J\in F_{b}\}\cup\{s(b+1)\}\]
Recalling the decomposition of \(F\) and the optimization program over it,
\[\max_{J\in F} f(J)=\text{max}(f(\emptyset),\max_{b\in I}\max_{J\in F_b}f(J))\]
Recall the relation between \(F_{b+1}\) and \(F_{b}\)
\[\max_{J\in F_{b+1}}f(J)=\text{max}(\max_{J\in f_b}(f(J)+s(b+1)),s(b+1))\] \[\max_{J\in F_{b+1}}f(J)=\text{max}((\max_{J\in f_b}f(J))+s(b+1),s(b+1))\]
\(\text{max}(x+z,y+z)=\text{max}(x,y)+z\), so
\[\max_{J\in F_{b+1}}f(J)=\text{max}((\max_{J\in F_b}f(J)),0)+s(b+1)\]
This can be followed to a dynamic programming solution over the b axis. It’s very simple, so I’m not going to show code for it.
I’ve seen other "explanations" to this problem that use examples and heuristic thinking, but I don’t like those all that much. I’m happy with what I put together here because it follows a very neat pattern: decompose the set system (feasible set). (2) Put the pieces in relation with another. (3) Exploit the relation. This is more valuable than example churning and "guesswork-ish" dynamic programming relation ansatzes.
Here’s interesting extensions to this problem I thought about. What if \(s\) is an infinite sequence with some regularity condition tacked onto it, e.g. some recurrence holds over it, or it’s periodic. What if \(I\) is not a chain?