子数组奇偶索引元素之和的最大差
Maximum difference of sum of odd and even index elements of a subarray
给定一个包含 N 个整数的数组（可以是 positive/negative），计算任意 subarray，假设数组遵循 0 based 索引。
例如：
A = [ 1, 2, -1, 4, -1, -5 ]
最佳选择的子数组应该是：[ 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
如果你否定所有奇数索引元素，那么这个问题就变成了寻找最大（或最小）子数组和的问题之一。
Kadane's algorithm给出了解决此类问题的O(n)方法。
对于给定的示例：
# 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
给定一个包含 N 个整数的数组（可以是 positive/negative），计算任意 subarray，假设数组遵循 0 based 索引。
例如：
A = [ 1, 2, -1, 4, -1, -5 ]
最佳选择的子数组应该是：[ 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
如果你否定所有奇数索引元素，那么这个问题就变成了寻找最大（或最小）子数组和的问题之一。
Kadane's algorithm给出了解决此类问题的O(n)方法。
对于给定的示例：
# 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