子数组奇数和偶数索引元素之和的最大差值

Question

给定一个由 N 个整数组成的数组（可以是正数/负数），计算任何 subarray 的奇数和偶数索引元素之和的最大 difference，假设数组遵循 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 

Answer 1

如果你否定所有奇数索引元素，那么这个问题就变成了寻找最大（或最小）子数组和的问题之一。

Kadane 算法 给出了解决此类问题的 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

Answer 2

这是算法。另外，对于 hackerrank 问题，具有奇偶索引差的子数组和的最大平方。

private int findMaxSub(int[] arr) {
    int odd = 0, even = 0;
    for (int i = 0; i < arr.length; i++) {
        if (i % 2 != 0) {
            arr[i] = -arr[i];
        }
    }
    
    int best_sum = Integer.MIN_VALUE;
    int current_sum = 0;
    for (int x : arr) {
        current_sum = Math.max(x, current_sum + x);
        best_sum = Math.max(best_sum, current_sum);
    }
    
    for (int i = 0; i < arr.length; i++) {
        arr[i] = -arr[i];
    }
    int odd_best_sum = Integer.MIN_VALUE;
    current_sum = 0;
    for (int x : arr) {
        current_sum = Math.max(x, current_sum + x);
        odd_best_sum = Math.max(odd_best_sum, current_sum);
    }
    
    return Math.max(best_sum, odd_best_sum);
    // if question is (x - y)^2 then you do below
    //return Math.max(best_sum * best_sum, odd_best_sum * odd_best_sum);
}