每周一道算法题(四十)

本周题目难度级别"Easy",终于可以写下Python了，好久没写了，手都生了。。。

题目：给你一个数组，要求在所有相邻子序列中返回最大的相邻子序列的累加和。eg：给你一个数组[-2,1,-3,4,-1,2,1,-5,4]，它的最大相邻子序列为[4,-1,2,1]，返回累加和：6(4+(-1)+2+1)

思路：通过这道题，我发现不同的语言实现同一道题目的思路也会不同。因为不同的语言里面的“容器”会不同，比如C语言里没有字典的概念，你需要用链表或者map之类的容器，而其他很多语言都有Key-Value的容器。不扯远了，回到这题，先说下相邻子序列，就是子序列中的元素在母序列中的位置是相邻的，可以看题目中的例子来理解，至于思路是纯粹的数学，看下代码就OK了：

class Solution:
    def maxSubArray(self, nums):
        //记录最大的累加和
        result = nums[0]
        //临时记录相邻子序列的累加和
        temp = 0
        for num in nums:
            temp += num
            //如果累加和还没当前的数大，直接换掉
            if temp < num:
                temp = num
            //记录最大的相邻子序列累加和
            if temp > result:
                result = temp
        return result

效率还是很高的，当然，只是相对于Python来说，脚本语言嘛，你懂得。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!