剑指offer--algorithm14

题28--连续子数组的最大和

输入一个整型数组,数组里有整数也有负数。
数组中一二或连续的多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)

本题需要注意一点就是连续，而不是随机从数组中选取几个数来进行累加
书中介绍了两种解题的思路，第一种是通过举例来得到其中的规律，书中举例的数组为[1,-2,3,10,-4,7,2,5]

image.png
image.png

下面是本题的程序

"""
本题的for 循环短小精悍，却十分的巧妙
"""

class solution(object):
    def ngreatest(self,array):
        if array==None or len(array)==0:
            return None 
        cum=0#初始化一个值，用于跟踪叠加后的值的正负状况
        ncount=array[0]#用于存储连续数组的和的最大值
        for i in range(len(array)):
            if cum<=0:
                cum=array[i]#注意循环的结构，非[i+1]
            else:
                cum+=array[i]#注意这里也非[i+1]
            if cum>ncount:
                ncount=cum
        return ncount 
    
        




def main():
    s=solution()
    print (s.ngreatest([1,-2,3,10,-4,7,2,5]))
    
    
    
if __name__=='__main__':
     main()

第二种方法巧妙的应用了动态规划法，来处理此问题，该方法的思路解析如下

image.png

下面为该方法的程序和注释

class solution(object):
    def ngreatest(self,array):
        if array==None or len(array)==0:
            return None 
        storage_array=[0]*len(array)#该数组的作用是存储累加的数字，以【1，-2,3,10，-4,7,2,5】为例，那么存储的东西为[1,-1,3,13......]
        for i in range(len(array)):
            if i==0 or storage_array[i-1]<=0:
                storage_array[i]=array[i]
            else:
                storage_array[i]=storage_array[i-1]+array[i]
        return max(storage_array)



def main():
    s=solution()
    print (s.ngreatest([1,-2,3,10,-4,7,2,5]))
    
    
    
if __name__=='__main__':
    main()

题29--把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

本题其实就是一个排序题

"""
首先注意字符串的一个比较
其次注意冒泡算法
"""


class solution(object):
    def sorted_num(self,array):
        if array==None or len(array)<=0:
            return None 
        strnum=[str(m) for m in array]
        """"
        下面使用冒泡算法排序
        """
        for i in range(1,len(strnum)):
            for j in range(0,len(strnum)-i):
                if strnum[j]+strnum[j+1]>strnum[j+1]+strnum[j]:
                    strnum[j],strnum[j+1]=strnum[j+1],strnum[j]
        return ''.join(strnum)
    
    
    
    
    
def main():
    s=solution()
    print (s.sorted_num([23,15,42]))
    
    
    
    
    
if __name__=='__main__':
    main()