给定一个数组，数组中有正有负，求出连续数组中和值最大的数（数组长度大于等于1）

刷牛牛客遇到的题，想给出完整而又简洁的function（python解答，但是关键是思想，语言不是问题啦）

1.给定一个数组，数组中有正有负，求出连续

（全部都是正的时候，所有值累加就是最大值）

（全部为负的时候，max(array)就是我们想要的）

# -*- coding:utf-8 -*-



#import numpy 




class Solution:



    def FindGreatestSumOfSubArray(self, array):



        length =len(array)



        result =[]



        sort_max = []



        #1.全是正数的情况




        #2.全是负数的情况 




        #3.有正有负的情况




        for i in range(length-1): 



            for j in range(i+1,length): 



                (sum(array[i:j]))



            #全部为正时，所有累加起来就是最大的    




            (sum(array))



            #sort_ = sorted(result,reverse=False)




            #找出最大值




            sort_ = max(result)



            #把每次得到的最大值存放在sort_max中




            sort_max.append(sort_)



        return max(sort_max)       

2.从1-n 的正整数中出现 1 的次数：

例如 n = 11, 则 1,10,11 就出现了4次1（11算作两次，同理，111算作三次）

这里就是找出一个数学规律，这样时间复杂度最低

可以推广到任意数X：

 1 - 10，在它们的个位数中，任意的 X 都出现了 1 次。  1 -100，在它们的十位数中，任意的 X 都出现了 10 次。 1 -1000，在它们的百位数中，任意的 X 都出现了 100 次。1-10000，在它们的千位数中，任意的 X 都出现了 100 次。

........

1-10的i次方，在它的右边数第i 位，任意的 X 都出现了 10的(i-1)次。

代码实现如下：

# -*- coding:utf-8 -*-



#import numpy




from  math import*




class Solution:



    def NumberOf1Between1AndN_Solution(self, n):



        #找数学规律




        #n为负数(此题不考虑，它说了是非负整数)




        #if n < 0:




        #   return 0




        result=0




        tmp=n



        base=1




        while tmp:



            last=tmp%10




            tmp=tmp//10




            result+=tmp*base



            if last==1:



                result+=n%base+1




            elif last>1:



                result+=base



            base*=10




        return result