2018-05-25

还是算法导论，线性时间，最大子数组和，这里是探索代码简化，与代码局限

def maxSubArray( array):

    length = len(array) 
    boundry = array[0]
    print ( 'bound-1--'+str(boundry))
    
    maxArray = array[0]
    print ( 'maxArray-1--'+str(maxArray))
    
    #for(i in  i<length):
    for i in range(1, length):
        #print '===============================>>>'+str(i)+'>>>go'
    
        #if( boundry+array[i] >= array[i] ):
        # use math ,delete array[i] on the both side
        #if ( boundry  >= 0 ):
        # because  0  array[i] +0 = array[i] ,we can delete =
        #if ( boundry  > 0 ):
        #    boundry += array[i]
        #    print 'intoif-1=='+ str(boundry) 
        #else:
        #    boundry = array[i]
        #    print 'into-else-1=='+ str(boundry) 
        boundry =   array[i] if  boundry<0 else ( boundry+ array[i])
            
            
        #if( maxArray < boundry ):
        #    maxArray = boundry
        maxArray=max(maxArray,boundry)    
            
        #print 'into-ifmax-1=='+ str(maxArray) 
    
    return maxArray



#a=[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7,-99,88,12] 
a=[-13,-3,-25,-20,-3,-16,-23,-18,-20,-7,-12,-5,-22,-15,-4,-7,-99,-88,-12] 
print maxSubArray(a) 

#a=[-13,-3,-25,-20,-3,-16,-23,-18,-20,-7,-12,-5,-22,-15,-4,-7,-99,-88,-12]

def main():  
    
    max = max_subarray(a)  
    print max  
  
def max_subarray(a):  
    max_ending_here = max_so_far = 0  
    for x in a:  
        max_ending_here = max(0, max_ending_here + int(x))  
        max_so_far = max(max_so_far, max_ending_here)  
    return max_so_far  
  
      
if __name__ == "__main__" : main() 

result

$python main.py

-3
0

这里是两段代码，也就是两次，
注释里面，写明了，一步一步，把代码压缩到一行上的原因。
通过看到运行结果不一样，可以看出，第二段代码，如果整个数组都是负值，的情况下是不行的。
这就是局限性。
其中第二段，代码，参考 https://blog.csdn.net/bbsunchen/article/details/12366533
感谢作者，我们应该只在乎，在前人的肩膀上，进步了多少，而不是证明，我比你强。
或者发现别人的错误，而沾沾自喜。
如果站在别人的肩膀上，还没有别人看得远，才是我们应该反思的。

def maxSubArray( array):
    length = len(array) 
    boundry =maxArray =  array[0]
    for i in range(1, length):
        boundry = array[i] if  boundry<0 else (boundry+ array[i])
        maxArray=max(maxArray,boundry)     
    return maxArray
#a=[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7,-99,88,12] 
a=[-13,-3,-25,-20,-3,-16,-23,-18,-20,-7,-12,-5,-22,-15,-4,-7,-99,-88,-12] 
print maxSubArray(a)