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
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