Maximum alternating slice in an array

Question

I'm working on the problem:

Given array with positive and negative values, return the maximum alternating slice size; two elements are alternating if they have different signs, zero is treated as both negative and positive.

Time complexity: \$O(N)\$

Space complexity: \$O(1)\$

I developed a working code and would like to know if there is any method to make the code shorter or faster.

public static int maxSizeAlterSlice(int[] a){
    int max_size_so_far = -1;
    int cur_max_size = -1;
    if(a.length == 1)
        return 1;
    int startInd = 0;
    int endInd = 0;
    int i=1;
    int compareInd=0;
    while(i<a.length){
        if((a[compareInd]>=0 && a[i]<=0)||(a[compareInd]<=0 && a[i]>=0)){
            compareInd=i;
            endInd++;
            i++;
        }else{
            cur_max_size = endInd-startInd+1;
            if(max_size_so_far<cur_max_size){
                max_size_so_far = cur_max_size;
            }
            startInd = i;
            compareInd=startInd;
            endInd=startInd;
            i=startInd+1;
        }
    }
    return max_size_so_far;
}

I get the result -1 for the array {-1, 1} with your code ... — Martin R
– Martin R, Commented Oct 24, 2017 at 11:33
Are you going to fix this? CR is about reviewing working code. – Btw, does -1, 0, 1 count as an alternating sequence of length 3? — Martin R
– Martin R, Commented Oct 24, 2017 at 13:00
If zero is both negative and positive; are 1, 0, 1 and 1, 0, -1 both valid alternating sequences? — CiaPan
– CiaPan, Commented Oct 24, 2017 at 15:45
@SarahM: Note that incorporating feedback from an answer into the question is not allowed on this site, please see What to do when someone answers and what you may and may not do after receiving answers. — Martin R
– Martin R, Commented Oct 25, 2017 at 6:50
I've rolled back you question to Rev 2, as you still included some of wildbagel's advice in your question. — Peilonrayz
– Peilonrayz ♦, Commented Oct 25, 2017 at 8:13

wildbagel · Accepted Answer · 2017-10-24 13:50:51Z

Hmm. I'm not sure about faster, but you can shorten your code by about 6 lines by doing things a little more efficiently.

First, I'd move your two initializations at the top to be below your if statement. That if statement short-circuits the whole function (which is fine), but since the statement doesn't use those two variables, we shouldn't instantiate them unless it fails to return: that's more efficient. I would also return a.length rather than 1 (to eliminate a 'magic number').

Next, you can eliminate the cur_max_size variable and its usage. Remove the declaration, then take the whole block involving cur_max_size and max_size_so_far and replace with this:

max_size_so_far = Math.max(endInd - startInd + 1, max_size_so_far);

Next, there are two places where you can use i++ inside of another statement, rather than having it stand on its own. i++ means "increment after the original value is used" so this is safe:

Inside of your if conditional (inside the while), delete i++; and change the first statement to be compareInd = i++;
Inside of your else statement, remove i = startInd + 1; and change the startInd=i; line to be startInd = i++;. (Yes, the logic works out.)

vnp · Accepted Answer · 2017-10-24 17:00:39Z

Give your operators some breathing space.
compareInd is confusing. Logically, it is always equal to i - 1, but it is quite hard to infer from the code. Better drop it entirely, and explicitly use i - 1.
endInd is equally confusing. It also follows i, and therefore is unnecessary as well.

The if...else construct begs to become a loop:

    while (i < a.length) {
        while (alternating(i)) {
            i++;
        }
        length = i - startInd;
        ....
        startInd = i++;
    }

Now it becomes obvious that the outer while is in fact a for:

    for (i = 1; i < a.length; i++) {
        while (alternating(i)) {
            i++;
        }
        ....
        startInd = i;
    }

An alternation condition could be simplified as a[i-1] * a[i] <= 0, but it is a matter of taste.

Depending on the range of the given numbers, a[i-1] * a[i] can overflow. One could cast them to long to be on the safe side. — Martin R
– Martin R, Commented Oct 24, 2017 at 17:37

Stack Exchange Network

Maximum alternating slice in an array

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Maximum alternating slice in an array

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions