CODEWITHSUNDEEP
algorithmmathdynamic-programmingsub-array
Parth Pratim Chatterjee
Parth Pratim Chatterjee

Reputation: 43

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

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

Upvotes: 1

Views: 1968

Answers (2)

yash patel
yash patel

Reputation: 1

Here is algorithm. Also for hackerrank question maximum square of subarray sum with odd even index difference.

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);
}

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

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

Upvotes: 4

Related Questions