金乌智能--数据抓取、数据采集、爬虫

让每个人都轻松拥抱爬虫技术,拥有大数据技术!

子数组的最大累加和问题

数组、面试、刷题


题目描述

给定一个数组arr,返回子数组的最大累加和
例如,arr = [1, -2, 3, 5, -2, 6, -1],所有子数组中,[3, 5, -2, 6]可以累加出最大的和12,所以返回12.
[要求]
时间复杂度为O(n)O(n),空间复杂度为O(1)O(1)
 
示例1

输入

[1, -2, 3, 5, -2, 6, -1]

返回值

12

解题思路:本题的难点在于连加后小于0如何处理,为了求最大和,连加小于0可以置0

#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        if not arr:
            return 0
        res = arr[0]
        cur = arr[0]
        for i in arr[1:]:
            cur  += i
            if cur < 0:
                cur = 0
            else:
                if cur > res:
                    res = cur
        return res 

这个是我写的算法,易懂,但效率差点,直接附上高效的算法,不解释

#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        num = 0
        for i in arr:
            if num + i >=0:
                num +=i
            else:
                num = 0
        return num

博文最后更新时间:


评论

  • 暂无评论

发表评论

博客统计

访问量:99549

博文总数:112 评论总数:0

原创112 翻译0 转载0