Maximum Alternating slice size


  • 1
    M

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

    Example
    Given a = [1, -5, 23, 0, 1, 1, 0, 2, -5, 3, -1, 1, 2, 3] return 7 (the sequence [1, 0, 2, -5, 3, -1, 1] has maximum alternating slice size )

    The expected runtime is o(n).


  • 0

    @memoryless what should be the result in case we have [1, -5, 23, 0, 1, 1, 0, -2,- 5, 3, -1, 1, 2, 3]? How is treated 0? Do wee need to pay attention on the 0-s or only to insert them in maximum subsequence?


  • 0
    M

    @elmirap It should be 5, the maximum alternating sequence should be [1, -5, 23, 0, 1]


  • 0

    @elmirap I guess 0 can be treated as either positive or negative.


  • 0

    With other words 0 is treated as negative if it is between two positiive and vice verse in max subsequence? Is it right?


  • 0

    @memoryless

    Is the answer for input [0, 0, 0, 0, 0] = the entire array itself?


  • 0
    M

    @elmirap yes, I think you will always would append 0's to your .


  • 0
    M

    @1337c0d3r yes.


  • 2

    In case [1,0,-1] maybe we should exclude 0, because there is odd number of 0 between 1 and -1. 0 coudn't b treated 1 and -1 in the same time


  • 0
    This post is deleted!

  • 0

    @memoryless I believe that result in [1, -5, 23, 0, 1, 1, 0, -2,- 5, 3, -1, 1, 2, 3] is 9.
    Possible result is : 1, -5, 23, 0, 1, 0, 3, -1, 1

    Also for 1, -5, 23, 0, 1, 1, 0, 2, -5, 3, -1, 1, 2, 3 Result is 11
    Result : 1,-5,23,0,1,0,2,-5,3,-1,1

    Ofocurse if we take 0 for negative or positive depending on the subsequence

    Here is my code. zigzag dp modification O(n^2)

    void maxAlternatingSubseq(int[] nums) {
         int[] f1 = new int[nums.length];
         int[] f2 = new int[nums.length];
         if (nums[0] >=0)
             f1[0] = 1;
         if (nums[0] <=0)
             f2[0] = 1;
         for (int i = 1; i < nums.length; i++) {
             for (int j = 0; j < i; j++) {
                 if (nums[i] <= 0 && f1[j] > f2[i] ) {
                     f2[i] = f1[j];
                 }
                 if (nums[i] >= 0 && f2[j] > f1[i] ) {
                     f1[i] = f2[j];
                 }
             }
             f2[i]++;
             f1[i]++;
         }
         int max =0;
         for (int i = 0; i < nums.length; i++) {
             if (f2[i] > max) {
                 max = f2[i];
             }
             if (f1[i] > max) {
                 max = f1[i];
             }
         }
         System.out.println(max);
     }
    

  • 0

    @elmirap I believe from @memoryless example it's mentioning contiguous sequence (ie, substring), not subsequence. I'll let @memoryless to confirm.


  • 0

    I see. That's even easier . Thanks


  • 0
    M

    @elmirap said in Maximum Alternating slice size:

    In case [1,0,-1] maybe we should exclude 0, because there is odd number of 0 between 1 and -1. 0 coudn't b treated 1 and -1 in the same time

    I think this should be 2, the max slice is [1,0] or [0,-1]


  • 0
    M

    @1337c0d3r said in Maximum Alternating slice size:

    @elmirap I believe from @memoryless example it's mentioning contiguous sequence (ie, substring), not subsequence. I'll let @memoryless to confirm.

    Yes, the word slice means contiguous sequence.


  • 0

    thank you very much @memoryless


  • 0

    @andyreadsall could you test your algorithm for this input [1,0,0,2,-3] it returns 3, but answer is 0,0,2,-3 ( +,-,+,-)
    Here is my implementation. The idea is to count the number of consecutive zeros and to keep previous non zero number. Using this information we extend max contiguous array or start searching for new max contiguous array.
    Conditions to extend :

    1. We have alternating non zero numbers, e.g 1, -1, 2, - 3
    2. We have numbers with same sign and zeros between them
      1 0 0 0 3
      -1 0 0 0 0 - 4
      In the first case when zeros are odd number we can extend max subarray till 3 inclusively
      In the second case when zeros are even number it is not possible to extend. We start to search for new max subarray.
    3. We have numbers with different sign and zeros between them
      1 0 0 0 -3
      -1 0 0 0 0 4
      In the first case when zeros are odd number it is not possible to extend. We start to search for new max subarray.
      In the second case when zeros are even number we can extend max subarray till 4 inclusively

    Please try testcase [ 0, 0, 0,0,0,-1,2,-3,4,0,0,0,0,0,-5,6,0,0,0,0]

    public int maxAlternatingSubarray(int[] a)  {   
        if  (a.length  <=  1)
            return a.length;
        int curRes = 0;
        int maxRes = 0;
        int i = 0;
        while (i  <  a.length && a[i]  ==  0)   {
            curRes++;
            i++;
        }
        if  (i  <  a.length)  {            
            int zeros = 0;
            int prevNonZero  =  a[i];
            curRes++;
            i++;
            while  (i  <  a.length)  {
                if  (a[i]  ==  0)  {
                    curRes++;
                    zeros++;
                } else {
                    if  ((a[i]  >  0  &&  prevNonZero  >  0)  ||  (a[i]  <  0  &&  prevNonZero  <  0))  {
                        if  (zeros  >  0)  {
                            if  (zeros % 2  ==  1)
                                curRes  +=  1;
                            else {
                                maxRes  =  Math.max(maxRes,  curRes);
                                curRes  =  zeros  +  1;
                            }
                            zeros  =  0;
                        }
                        else {
                            maxRes  =  Math.max(maxRes,  curRes);
                            curRes  =  zeros  + 1;
                        }
                    }
                    else {
                        if  (zeros  ==  0) 
                            curRes++;
                        else {
                            if  (zeros%2  ==  0)  {
                                curRes  +=  1;
                            }
                            else {
                                maxRes  =  Math.max(maxRes, curRes);
                                curRes  =  zeros + 1;
                            }
                            zeros  =  0;
                        }
                    }
                    prevNonZero  =  a[i];
                }
                i++;
            }
        }
        maxRes  =  Math.max(maxRes, curRes);
        return maxRes;
     }

  • 0
    R

    I split the problem into 2 parts:

    • find when there is an alternation (1) or (0)
    • count the maximum contiguous sequence of 1
    def maxAlternatingSlice(nums):
    
        def _iter():
           cur = 0
           for next in nums:
              yield int(cur * next <= 0)
              cur = next
    
        best = acc = 0
        for x in _iter():
           acc = (acc + x) * x
           best = max(best, acc)
        return best

  • 0
    K
    public static int solution(int[] A) {
        
    		int maxP = 0; // cur length of alternating slice , ending in +ve number
    		int maxN = 0; // cur length of alternating slice , ending in -ve number
    		int max;
    		
    		if(A[0] >= 0) maxP = 1;
    		if(A[0] <= 0) maxN = 1;
    		max = Math.max(maxP, maxN);
    		
    		for(int i=1;i<A.length;i++)
    		{
    			if(A[i] > 0)
    			{	maxP = maxN + 1; maxN = 0;}
    			else if(A[i] <0)
    			{	maxN  = maxP +1; maxP = 0;}
    			else
    			{
    				int prevMaxP = maxP;
    				maxP  = maxN  +1;
    				maxN = prevMaxP + 1;
    			}
    			max = Math.max(max,Math.max(maxN, maxP));
    		}
    		return max;
    	}
    

  • 1
    L

    @memoryless
    See a simple Java solution below:

        public int maxAltSliceSize(int[] nums){
            int max = 0;
            for(int i=0, j=1; j<nums.length; j++) {
                if( (long)nums[j] * (long)nums[j-1] >0) {
                    max = Math.max(max, j-i);  //j-i is the count of current alternating slice size.
                    i = j;
                }
            }
            return max;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.