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".

• dariosicily: Welcome to Stack Review, I understand how you find the subarrays of one array like the title of your question, but I don't understand the part about sum of even and odd elements.
• Adil: I have updated the question
• Pavlo Slavynskyy: This doesn't help. Is that an explanation of the code or the correction to the task? If you have the task to find subarrays - you can throw out that even/odd sum part, the code will be much more efficient. If you have the task of "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" - then you're doing exactly what is said, no optimization possible.
• Adil: Have added required clarifications.
• greybeard: It is helpful and customary to put the introduction first: How do I ask a Good Question? If this is a 3rd party programming challenge, please hyperlink and tag accordingly.

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.

• greybeard: You increment j and m (declare in same place as j!) in lockstep - they will stay the same. I think the intention was to have m represent the index in the current subarray: just increment it "in the if". Just use one sum, conditionally adding to and subtracting from it. Or try to find a "branch free" variant.
• Pavlo Slavynskyy: I was trying to transform Adil's code keeping it close to the original.
• greybeard: (trying to [keep the code] close to the original fair enough; but as is, m is not the index in the sub-array/"conceptual inner List".)