最大子段和_算法与数据结构_Python
时间:2011-04-25 来源:追求卓越 挑战极限
今天有幸参加了腾讯实习的一面,估计也是最后一面了,很少写代码了,写也是用matlab在搞些图像方面的处理。
面试官让我做了下简单的自我介绍,然后扫了下我的简历,让我写一个最大子段和的代码。我问他语言不限吧,他迟疑了下,然后说可以,悲剧从此诞生,我用python弄了个最大子段和的程序,这是个动态规划的程序不算太难,他看不懂,让我写一个c语言的反转字符串程序,哈哈,估计把他逗了吧,但是我应该也是悲剧了。
最大子段和的程序就不用介绍了,下面的解答有点bf的意思。
python代码:
def SetSubSum(array,index): #获取每个子段和 global sums if sums[index-1]>=0: sums[index] = sums[index-1] + array[i] else: sums[i]=array[i] def GetMaxSum(array): #获取最大子段和 _max = array[0] for i in range(1,len(array)): if _max<=array[i]: _max=array[i] return _max if '__name__=__main__': array = [1,2,-2,3,4] global sums sums = [0]*len(array) for i in range(0,len(array)): SetSubSum(array,i) _max = GetMaxSum(sums) print("Max Sub Sum is:",_max)
相关阅读 更多 +