Maximum sum after splitting into subarrays taking difference of maximum and minimum of each one
Some case analysis shows that:

Without loss of generality, every subarray is monotone.
Without loss of generality, no monotone subarray is &quot;broken&quot;, that is, joining two adjacent subarrays cannot result in a monotone subarray.

This reduces the number of options in dynamic programming to $O(1)$, and so should lead to an $O(n)$ algorithm.
(It seems that some case analysis is still needed. For example, if the array is $a,b,c$, where $a&lt;b&gt;c$, then the best solution depends on whether $a&lt;c$ or $a&gt;c$.)