# Find maximum length of array where every entries are the same

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)

• 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! Feb 15, 2019 at 21:17
• 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. Feb 15, 2019 at 21:38
• 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. Feb 15, 2019 at 21:55
• It is not a challenge. It is my assignment actually . It is my first day to use stackexchange. really sorry for causing any inconvenience Feb 15, 2019 at 23:01
• What is the expected result for A = [3,2,4,2,4,2,4,5,3]?
– vnp
Feb 16, 2019 at 0:50

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)


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)

• wow so is the itertools installed in python? and what is the itertools really for? Feb 16, 2019 at 17:05
• @WingHoLo Yes it's installed with Python. It's a collection of functions to help with iterators. Feb 16, 2019 at 17:08

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)

• I'm confused where the Code Review is. Also this code looks needlessly long. Feb 16, 2019 at 11:56
• I only focused on the complexity. Feb 16, 2019 at 12:57
• so here we return 4 elements in a function. But it cannot be done in python or any programming at all right? Feb 16, 2019 at 17:07