Size of the largest subsequence of values with consecutive alternative sign?-CodePudding

Is there a short way to detect the longest sublist with alternative signs within a list?

For instance:

my_list = [-1, -0.5, 1, -3, 4, 5, 5, -1]

returning 4 starting from -0.5 to 4?

This is what I have written so far but I feel there is room for something much shorter.

import numpy

my_list = [-1, -0.5, 1, -3, 4, 5, 5, -1]

# function that detects whether a list has alternate signs
# https://stackoverflow.com/questions/6451514/detect-alternating-signs
def is_alternating_signs(a):
    return numpy.all(numpy.abs(numpy.diff(numpy.sign(a))) == 2)

# getting all sublists from the main list
sublists = []
for i in range(len(my_list)   1):
      for j in range(i   1, len(my_list)   1):
          sublists.append(my_list[i:j])

# detecting the longest sublist with alternate signs
max_list = 0
for sublist in sublists:
      if is_alternating_signs(sublist) and len(sublist) > max_list:
          max_list = len(sublist)
print(max_list)

CodePudding user response：

Use zip to compare the current element with the next one:

maxlen = 1
curlen = 1
for i, j in zip(l, l[1:]):

    # if one conditions match
    # increment curlen by 1
    if (i < 0 and j > 0) or (i > 0 and j < 0):
        curlen  = 1

    # break the alternative sign
    # keep the highest value between maxlen and curlen
    # reset curlen to 1
    else:
        maxlen = max(maxlen, curlen)
        curlen = 1
maxlen = max(maxlen, curlen)

Output:

>>> maxlen
4

CodePudding user response：

You can use zip to detect the positions of 'breaks' in the alternance. Then combine these breaks into ranges to find the longest streak of alternating values:

L = [-1, -0.5, 1, -3, 4, 5, 5, -1]

breaks  = [i for i,(a,b) in enumerate(zip(L,L[1:]),1) if (a<0)==(b<0)]
longest = max((L[s:e] for s,e in zip([0] breaks,breaks [None])),key=len)

print(longest)
[-0.5, 1, -3, 4]

If you're only looking for the length of the streak, you could convert the zip result to a string of 1s and 0s, then split on 0s and measure the longest substring:

max(map(len,"".join("01"[a*b<0] for a,b in zip(L,L[1:])).split('0'))) 1 

4

CodePudding user response：

What about a single loop?

def max_alt_subseq_size(seq):
    last_x = seq[0]
    size = max_size = 1
    for x in seq[1:]:
        # use the fact that x * y < 0 iff x > 0 and y < 0 or x < 0 and y > 0
        if last_x * x < 0: 
            size  = 1 
        else:
            # once the size of the alternating subsequence is found, we need to check if it is the largest
            if size > max_size: 
                max_size = size
            size = 1 
        last_x = x
    # check on the final subsequence to see if it is the largest
    if size > max_size: 
        max_size = size
    return max_size


my_list = [-1, -0.5, 1, -3, 4, 5, 5, -1]
max_alt_subseq_size(my_list)
# 4

CodePudding user response：

One could have a (number of) fully vectorized approach.

The code below assumes a NumPy 1D array as input.

For example, if one computes the

(Full analysis here).