Commando - Problem Statement

Split $n$ soldiers into contiguous groups. Group value = $a \cdot x^2 + b \cdot x + c$ where $x$ is sum of strengths in group. $dp[i]$ = max value for first $i$ soldiers.

Transition: $dp[i] = \max_{j < i}(dp[j] + f(S_i - S_j))$ where $S$ is prefix sum. Expand $f(S_i - S_j) = a(S_i - S_j)^2 + b(S_i - S_j) + c$. Separate terms by $i$ and $j$. Result: linear in $S_i$ with slope depending on $j$. Apply CHT. Handle max instead of min by negating.