Kadane's Algorithm

Standard tabulation gets you `O(n^2)` DP. The Convex Hull Trick brings the same recurrence down to `O(n log n)` whenever the transition is a linear function of the previous state, and the speedup matters: contest problems with `n = 10^5` go from too-slow to fast enough on exactly that change. A whole sub-field of DP is dedicated to these recurrence-shaped optimizations, and this lesson is your entry into it. **Advanced DP Techniques** covers four directions of post-tabulation DP. Optimization methods include the Convex Hull Trick (offline sorted-slope and online Li Chao tree), Divide and Conquer DP for monotone-split problems, and Knuth's Optimization for optimal-BST-style recurrences. Digit DP teaches you how to count numbers with properties in a range `[L, R]` by carrying a tight-constraint flag through the recursion. Advanced bitmask DP solves TSP, Hamiltonian path, and grid-tiling profile DP. Probability DP turns recurrences over expected values into clean tables, and Kadane's algorithm generalizes to circular and 2D variants. In **Dynamic Programming (Advanced)**, you mastered multi-dimensional state and transitions. This lesson asks the next question: when the table is too big or the transition too slow, how do you optimize? Next, **Graph Algorithms (Advanced)** brings similar depth to graph theory.