Find maximum length of array where every entries are the same

Question

Is the complexity of this code \$O(n^3)$? How can I improve the efficiency and reduce the complexity?

A = [3,2,4,2,4,2,4,5,3]
n= len(A)
def ALG2 (A,i,j): #to check whether all entries between A[i] and A[j] are the same
 if i==j:
 return True 
 for k in range (i,j-1):
 if A[k] != A[k+1]: 
 return False
 return True
def ALG1(A,n): #find the max length of the arrays that are found in ALG2 
 l=0
 for i in range (0,n-1):
 for j in range (i+1,n-1): 
 if ALG2(A,i,j) and (j-i)>l:
 l= j-i
 return l
result = ALG1(A,n)
print (result)

• Peilonrayz: I'm not sure why this has a down vote :( Could you add a little more description on what this code is doing? If this is a programing challenge including the challenge description and a link would be all that's needed!
• Caperneoignis: Yes, I believe if you have a loop in a function being called inside of a loop you must also add that as a nested loop.
• Sᴀᴍ Onᴇᴌᴀ: Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to edit and give it a different title if there is something more appropriate.
• Wing Ho Lo: It is not a challenge. It is my assignment actually . It is my first day to use stackexchange. really sorry for causing any inconvenience
• vnp: What is the expected result for A = [3,2,4,2,4,2,4,5,3]?

Answer 1

1. You should use better function names ALG1 and ALG2 don't really say what they're performing.
2. You should keep the creation of A, n and result at the bottom of your code.

3. You should keep your 'main' code in a main guard block:

   if __name__ == '__main__':
    A = [3,2,4,2,4,2,4,5,3]
    n= len(A)
    result = ALG1(A,n)
    print(result)
   

4. You should follow PEP 8, so that it's easier for others to read your code.

5. ALG2 can be simplified by slicing the array from i to j, A[i:j], and then checking if the set has a size of one.

   def ALG2(A, i, j):
    return len(set(a[i:j])) == 1
   

6. Your entire code can be drastically simplified by using itertools.groupby.

   import itertools
   def ALG1(array):
    sizes = (
    sum(1 for _ in g)
    for _, g in itertools.groupby(array)
    )
    return max(sizes, default=0)
   

• Wing Ho Lo: wow so is the itertools installed in python? and what is the itertools really for?
• Peilonrayz: @WingHoLo Yes it's installed with Python. It's a collection of functions to help with iterators.

Answer 2

Your algorithm is indeed n^3, but you can do it in linear time. https://ideone.com/Ke3q5o

A = [3,2,5,4,4,4,4,2,4,4]
def findLongestContinuousSection(A):
 if len(A) == 0:
 return
 longestStart = 0
 longestStop = 0
 longestLength = 0
 longestVal = 0
 curStart = 0
 curStop = 0
 curLength = 1
 curVal = A[0]
 for k in range(1,len(A)-1):
 if curVal != A[k]: # record cur as longest
 longestVal = curVal
 longestStart = curStart
 longestStop = curStop
 longestLength = curLength
 curStart = k
 curStop = k
 curLength = 1
 curVal = A[k]
 else: # continue to build current streak
 curStop = k
 curLength += 1
 return (longestStart, longestStop, longestLength, longestVal)
print findLongestContinuousSection(A)

• Peilonrayz: I'm confused where the Code Review is. Also this code looks needlessly long.
• user2966394: I only focused on the complexity.
• Wing Ho Lo: so here we return 4 elements in a function. But it cannot be done in python or any programming at all right?