Maximum sum after splitting into subarrays taking difference of maximum and minimum of each one I was asked this in a hiring challenge that I gave today on HackerEarth:
Question/Problem statement:
Given an array, split them into several subarrays(possibly zero) such that you obtain maximum sum of difference between maximum and minimum in each of those subarrays.
Examples:
[1, 2 , 1 , 0, 5]

You can split them into 3 subarrays [1,2] , [1],  [0,5].
Through this split, you can obtain maximum sum like (2-1) + (1-1) + (5-0) = 6.
Another example:
[1,4,2,3]

You can split them into 2 subarrays [1,4] , [2,3].
Through this split, you can obtain maximum sum like (4-1) + (3-2)  = 4
Constraints:

Array length can be up to 106.
Array values can be between -109 to 109.

My attempt:
I made a brute force DP attempt which was partially accepted. Below is the approach.
long[] dp = new long[N + 1];
 
for(int i = N-1;i &gt;= 0; --i){
    dp[i] = 0;
    int min = A[i],max = A[i];
    for(int j = i; j &lt; N; ++j){
        min = Math.min(min, A[j]);
        max = Math.max(max, A[j]);
        dp[i] = Math.max(dp[i],max - min + dp[j + 1]);
    }
}
 
print(dp[0])

Issue:
Can anyone share with me how this can be solved efficiently?
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$.)