Optimal way to find maximal sum (with constraints) of array elements
This is a classic Dynamic Programming problem. Basically, dynamic programming is a way of turning a recursive algorithm into an iterative one with better runtime, by saving previous results that we might need again.

In this case, we can write the problem as two recursive functions:

maxSumSubtractFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Two options: take whichever is better
        -A[startIndex] + maxSumAddFirst(startIndex+1), # Use this one
        maxSumSubtractFirst(startIndex+1) # Skip this one
    )

maxSumAddFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Same as above
        A[startIndex] + maxSumSubtractFirst(startIndex+1),
        maxSumAddFirst(startIndex+1)
    )


In other words, we have two choices for each element: either include it (and flip the sign for the next one), or skip it (and keep the sign the same).

Now, we could run maxSumSubtractFirst(0) and get the answer that way, but this could take $O(2^n)$ in the worst case. We can do better.

Since each function will always return the same output given the same input, we can make two arrays the same length as our input, then store the results of maxSumSubtractFirst in one, and maxSumAddFirst in the other. If we start from the end (the largest index) and work backward, we'll never have to recurse at all: just look up the results in the array, which takes $O(1)$.

Now we can take the first element in the maxSumSubtractFirst array, and that's our answer. We've only had to call each function $n$ times, and each call takes $O(1)$, so this version of the algorithm runs in $O(n)$—a significant improvement over $O(2^n)$!

(Note that, as written, this only gets you the value of the sum, not the sequence of choices that led to it. But that's easy to change: make additional arrays to hold the choices, and fill them in with each call to maxSum*First.)