Maximum difference of sum of odd and even index elements of a subarray

Question

Given an array of N integers (can be positive/negative), calculate the maximum difference of the sum of odd and even indexed elements of any subarray, assuming the array follows 0 based indexing.

For Example:

A = [ 1, 2, -1, 4, -1, -5 ]

Optimally selected subarray should be : [ 2, -1, 4, -1 ]

   sum of even indexed elements (0 based) : 2 + 4 = 6

   sum of odd indexed elements (0 based)  : (-1) + (-1) = -2

                        Total Difference  : 6 - (-2) = 6 + 2 = 8 

Answer 1

If you negate all the odd indexed elements, then this problem becomes one of finding the maximum (or minimum) subarray sum.

Kadane's algorithm gives an O(n) method of solving such a problem.

For the given example:

# Original array
A = [1,2,-1,4,-1,-5]
# negate alternate elements
B = [-1,2,1,4,1,-5]
# maximum subarray
max_value = 2+1+4+1 = 8
# minimum subarray
min_value = -5
# biggest difference in subarray
max(max_value,-min_value) = max(8,--5) = max(8,5) = 8