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 >= 0; --i){
    dp[i] = 0;
    int min = A[i],max = A[i];
    for(int j = i; j < 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 "broken", 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 $ac$, then the best solution depends on whether $ac$.)

StackExchange Computer Science Q#136239, answer score: 5