Calculate square of (sum of even-indexed) - (sum of odd-indexed) subarrays from an array

Question

Find all subarrays from a given array in the least possible time complexity.

Requirement:
calculate the square of (sum of even-indexed elements) - (the sum of odd-indexed elements) of al the subarrays.

Explanation of above code:
I am iterating the array, and inserting all elements of the subarray in the innerList. Then, summing up all the even-indexed and odd-indexed elements separately. Subtracting the even and odd sum, and calculating its square.

What I am looking for:
Optimization for the code.

My Solution:

public static void subarr2(int[] arr) {

    int N = arr.length;
    int set_size = (int) Math.pow(2, N);

    List<List<Integer>> list = new ArrayList<>();
    List<Integer> innerList = null;

    int evnSum = 0, oddSum = 0, finalSum = 0;
    Set<Integer> sums = new TreeSet<>(Comparator.reverseOrder());

    for (int i = 1; i < set_size; i++) {
        innerList = new ArrayList<>();
        for (int j = 0; j < N - 1; j++) {
            int temp = (int) (1 << j);
            if ((i & temp) > 0) {
                innerList.add(arr[j]);
            }
        }
        innerList.add(arr[N - 1]);
        if (innerList.size() > 1) {
            list.add(innerList);
            evnSum = oddSum = 0;
            for (int m = 0; m < innerList.size(); m++) {
                if (m % 2 == 0)
                    evnSum += innerList.get(m);
                else
                    oddSum += innerList.get(m);
            }
            System.out.println("evnsum=" + evnSum + " subarr=" + innerList);

            finalSum = Math.subtractExact(evnSum, oddSum);
            sums.add((int) Math.pow(finalSum, 2));
        }

    }

    System.out.println("Output=" + sums.stream().findFirst().get());

}

I want to know, if this code can be further optimized? or made more full proof to cover any corner-case scenarios?

Some of the test cases failed saying "Time limit exceeded > 4s".

Answer 1

This problem can be treated as a candidate for Kadane's algorithm after odd indexed elements are negated.

1. Original array A = [1,2,-1,4,-1,-5]
2. negate odd indexed elements B = [1,-2,-1,-4,-1,5] Once you do this you can use Kadane's algorithm to find the max sum of subarrays and min sum of subarrays. The result that you are looking for will be the Squareof(max(max_value,-min_value))
3. maximum subarray max_value = 5
4. minimum subarray min_value = -2-1-4-1=-8
5. biggest difference in subarray max(max_value,-min_value) = max(5,--8) = max(5,8) = 8
6. so the final result you are looking for will be square of 8 = 64;

Solution:

import java.util.*;

public class Subarrays {
    
    public static void main(String[] args)
    {
        int[] arr= {1,2,-1,4,-1,-5};
        System.out.println(findMaxArrayValue(arr));
    }
    
    public static long findMaxArrayValue(int[] arr)
    {
        long max=0;
        //negate odd indexed elements
        for(int i=1;i<arr.length;i+=2)
        {
            arr[i]=0-arr[i];
        }
        //Use Kadanes Algorithm to find max of (max sum of subarrays and 0-min sum of subarrays)
        max=findMaxMinKadanesAlgo(arr);
        return max*max;
        
    }

    private static long findMaxMinKadanesAlgo(int[] arr) {
        // TODO Auto-generated method stub
        long maxSoFar = arr[0];
        long currMax = arr[0];
        long currMin = arr[0];
        long minSoFar = arr[0];
     
        for (int i = 1; i < arr.length; i++)
        {
            currMax = Math.max(arr[i], currMax+arr[i]);
             maxSoFar = Math.max(maxSoFar, currMax);
             if (currMin > 0)
                    currMin = arr[i];
                else
                    currMin += arr[i];
                 
                minSoFar = Math.min(minSoFar,currMin);  
        }
        return Math.max(Math.abs(maxSoFar), Math.abs(minSoFar));
        
        }
    }
```

Answer 2

int set_size = (int) Math.pow(2, N); is bound to result in zero for arr longer than Integer.size. (You use 1 << j later on: why switch?)

inserting all elements of the subarray in the innerList
is in dire need of explanation: "the subarray" is specified by (bits set in) i.

You posted an XY-problem:
The "real" problem seems to be to print the maximum square of the difference between the totals of even- and odd-indexed elements among all subarrays of a given array - smells dynamic programming.

Answer 3

Naming

Using consistent variable naming with full words usually is considered a good habit. Well, in a small part of the code like this using evnSum instead of evenSum can be justified by length of oddSum; but subarr2, set_size and oddSum shouldn't be used together. If you want to keep names, spell them as subArr2 (I hope you have subArr1 somewhere to justify it) and setSize. m is not a good name for a variable, too.

Overflowing

finalSum = Math.subtractExact(evnSum, oddSum); is not the only place where it can occur. If you care about overflowing - use other functions like Math.addExact all over.

Algorithm

You have \$O(n*2^n)\$ complexity (if you don't care about memory management), and I'm afraid this is the best you can do with this task.

Small optimizations

But still, you can do fewer operations in every loop. It doesn't look like you're using variable list anywhere - you're just copying data into it. So you can get rid of it with all data copy operations.

Next, what with innerList? First, you're filling it with data. Next, you're looping over it. You can combine two loops into one and cast innerList out:

evnSum = oddSum = m = 0;
for (int j = 0; j < N - 1; j++, m++) {
    int temp = (int) (1 << j);
    if ((i & temp) > 0) {
        if(m%2==0)
            evnSum += arr[j];
        else
            oddSum += arr[j]
    }
}

But, of course, you'll be unable to output evnSum before the whole innerList this way. If you need it - make innerList the simple array of size N and output just the part you're working on, up to m. You'll avoid memory allocation/deallocation this way.