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

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

CodePudding user response：

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.