Yuval's answer explains the initial intuition and analysis. Here is a detailed explanation and an efficient algorithm in Java.
Given a (sub)array $B$, let $\min(B)$ and $\max(B$) be its minimum element and maximum element respectively. $B$'s range is the interval $[\min(B), \max(B)]$. Let the difference of $B$ be $d(B)=\max(B)-\min(B)$.
Given $p$ that is a partition of the given array into subarrays, let $sd(p)$ be the sum of differences of those subarrays.
Splitting Lemma. Given partition $p$, two contiguous elements $n_1$ and $n_2$ in some (sub)array $B$ of $p$, let us split $B$ between $n_1$ and $n_2$ into subarrays $B_1$ and $B_2$, obtaining a new partition, which will be called $p'$. If both $n_1$ and $n_2$ are in $B_1$'s range or both are in $B_2$'s range, then $sd(p) \le sd(p')$.
Here is how to understand the lemma.
- Subarrays in $p$ other than $B$ are not changed; so their contribution to the sum of differences will not decrease.
- When $B$ is split into $B_1$ and $B_2$, the only part of the range of $B$ that might get "missing" is the interval $[\min(n_1, n_2), \max(n_1, n_2)]$. If that interval is covered by either $B_1$ or $B_2$, the sum of differences will not miss that range.
Let $p$ be some partition of the given array.
Suppose there is a peak in one of subarrays in $p$, i.e., three contiguous number $a,b,c$ such that $a<b$ and $b>c$.
- Suppose $a \le c$. We can split this subarray further into two subarrays by cutting between $b$ and $c$, arriving at partition $p'$. Since both $b$ and $c$ are in the range of the new subarray that contains $a$, $sd(p) \le sd(p')$.
- Otherwise $a \gt c$. Symmetrically to the above, we will cut between $b$ and $a$.
Suppose there is a valley in one of subarrays in $p$, i.e., three contiguous number $a,b,c$ such that $a>b$ and $b<c$.
- Suppose $a \ge c$. We can split this subarray further into two subarrays by cutting between $b$ and $c$, arriving at partition $p'$. Since both $b$ and $c$ are in the range of the new subarray that contains $a$, $sd(p) \le sd(p')$.
- Otherwise $a \lt c$. Symmetrically to the above, we will cut between $b$ and $a$.
The above shows that whenever a partition contains either a peak or valley in one of its subarrays, we can split that subarray to get a partition that is no less optimal.
In particular, cutting subarrays repeatedly if necessary, we can replace an optimal partition with another one that has no peak or valley in any of its subarrays.
Hence, in order to final the maximum sum, we only need to consider the partitions that has no peak nor valleys in all of its subarrays, i.e, each subarray is (weakly) increasing or (weakly) decreasing.
If two consecutive subarrays are, if considered together, is an increasing array or a decreasing array still, combining these two subarrays into one subarray will not decrease $sd$. So, we only need to consider subarrays each of whose endpoints is the endpoint of a maximal increasing run or a maximal decreasing run or its immediate neighbors.
Here is an implementation in Java that runs in $O(n)$ time. It should finish within half of a second when $n=10^6$.
static long maximumSum_simplified(int[] A) {
int len = A.length;
// maxSum[i+1] will be the max sum out of A[0..i] for selected `i`s.
long[] maxSum = new long[len + 1];
// maxSum[0] = 0; by Java default.
// A[start..end] will be a maximal increasing run or a maximal decreasing run.
for (int start = 0, end; start < len - 1; start = end) {
end = start + 1;
if (A[end] <= A[start]) {
while (end + 1 < len && A[end + 1] <= A[end]) end++;
for (int i = Math.max(end - 1, start + 1); i <= end; i++) {
maxSum[i + 1] = Math.max(maxSum[start] + A[start] - A[i],
maxSum[start + 1] + A[start + 1] - A[i]);
}
} else {
while (end + 1 < len && A[end + 1] >= A[end]) end++;
for (int i = Math.max(end - 1, start + 1); i <= end; i++) {
maxSum[i + 1] = Math.max(maxSum[start] + A[i] - A[start],
maxSum[start + 1] + A[i] - A[start + 1]);
}
}
}
return maxSum[len];
}