Leetcode 3578. Count Partitions With Max-Min Difference at Most K

Count the number of ways to split an array into one or more contiguous segments so that in every segment the difference between its maximum and minimum is at most k, returning the result modulo 1e9+7. With n up to 5·10^4 this requires an O(n)–O(n log n) approach (DP with a sliding-window/monotonic structure to track valid segment boundaries).