class LongestIncreasingSubsequence:
def getLIS(self, A, n):
# write code here
dp=[0 for i in range(n)]
dp[0]=1
max=0
print dp
for i in range(n):
now=0
if i!=0:
res=1
for j in range(i):
if A[i]>A[j]:
res=dp[j]
now=now +1
if now>=max:
max=now
dp[i]=res+1
else:
dp[i]=res
print dp
#return max(dp)
kk=LongestIncreasingSubsequence()
kk.getLIS([1,4,2,5,3],5)
其中dp 是一个以int类型为成员的list
而使用max()函数时却会报错
TypeError: 'int' object is not callable
是由什么原因导致的?
PHPz2017-04-18 09:24:28
Your max function is assigned a value of 0 in the fifth line, and the max function is overwritten. Rename your variable so that it does not have the same name as the library function
伊谢尔伦2017-04-18 09:24:28
The reason is as @rayleisure said, you use a variable of max
作為參考到 int
type here, resulting in
return max(dp)
Not only will the build-in function fail, but it will also cause:
TypeError: 'int' object is not callable
This is because you made a call to an integer max
,
In short, the naming of variable must not be inconsistent with:
keywords
build-in functions
The name of the standard library or any package/module in use
Same name.
The following are all off topic
Judging from your current code, it seems that you only need to write a function. Writing this class seems redundant (unless you are doing an online question bank?)
There is no need to pass in the length of the list. Asking about the length of the list in Python can be easily done with len()
For the LIS problem, I simplified your code:
Only find the length of LIS:
def lislength(lst):
"""O(n^2) by button-up method"""
n = len(lst)
dp = [1 for x in lst]
for i in range(n):
for j in range(i+1, n):
if lst[j] > lst[i]:
dp[j] = max(dp[j], dp[i]+1)
return max(dp)
The whole LIS is asking to come out:
def lis(lst):
"""O(n^2) by button-up method"""
# use prev to record the previous elements
n = len(lst)
dp = [1 for x in lst]
prev = [-1 for x in lst]
for i in range(n):
for j in range(i+1, n):
if lst[j] > lst[i]:
if dp[i]+1 > dp[j]:
prev[j] = i
dp[j] = dp[i]+1
# find last elements of LIS
maxl = maxpos = 0
for pos, l in enumerate(dp):
if l > maxl:
maxl, maxpos = l, pos
# trace back to find LIS
seq = []
while maxpos >= 0:
seq.append(lst[maxpos])
maxpos = prev[maxpos]
seq.reverse()
return seq
Test:
print(lislength([4,5,6,7,1,2,3,9]))
print(lis([4,5,6,7,1,2,3,9]))
print(lislength([1,3,6,7,4,5,9,10,15,12,14]))
print(lis([1,3,6,7,4,5,9,10,15,12,14]))
Result:
5
[4, 5, 6, 7, 9]
8
[1, 3, 6, 7, 9, 10, 12, 14]
Questions I answered: Python-QA