专栏首页Petrichor的专栏leetcode: 53. Maximum Subarray

leetcode: 53. Maximum Subarray

Problem

# Find the contiguous subarray within an array (containing at least one number) 
# which has the largest sum.
#
# For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
# the contiguous subarray [4,-1,2,1] has the largest sum = 6.
#
# click to show more practice.
#
# More practice:
#
# If you have figured out the O(n) solution, 
# try coding another solution using the divide and conquer approach, 
# which is more subtle.

AC

class Solution():
    def maxSubArray(self, x):
        if not x:
            return 0
        curSum = maxSum = x[0]
        for ele in x[1:]:
            curSum = max(ele, curSum+ele)
            maxSum = max(maxSum, curSum)
        return maxSum


if __name__ == "__main__":
    assert Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) == 6

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • nano:基本操作

    JNingWei
  • leetcode: 66. Plus One

    JNingWei
  • tensorflow: tf.reshape探究

      给定一个tensor,这个操作会返回一个有着跟原tensor一样的值且经过shape重塑过的张量。

    JNingWei
  • 电话拦截

    首先需要 android 源码文件NeighboringCellInfo.aidl和ITelephony.aidl,新建文件夹android.telephony...

    xiangzhihong
  • 如何在SAP WebClient UI里使用HANA Live report

    in popup window, you have to specify the following three attributes:

    Jerry Wang
  • 环境反向散射通信中断性能研究(CS)

    环境反向散射通信(AmBackComs)被认为是物联网的一种频谱和节能技术,因为它允许被动反向散射设备(BDs)将其信息调制成传统信号,例如蜂窝信号,并将它们反...

    蔡秋纯
  • HOJ-1005 Fast Food(动态规划)

    Fast Food My Tags (Edit) Source : Unknown Time limit : 3 sec Memory...

    ShenduCC
  • imp错误IMP-00098: INTERNAL ERROR: impgst2Segmentation fault

    如果使用impdp要看dump的内容,可以使用sqlfile参数,他会将所有的DDL语句写入文件,

    bisal
  • 并不简单的问题:列表与元祖有什么区别?

    花下猫说:公众号没有留言功能,真是不方便。上周,尝试性地推送了一篇英文文章,单从后台数据来看,效果还不错。这周继续尝试推送一篇。大家有什么想法,可以后台与我交流...

    Python猫
  • SAP UI5的Component-preload.js是啥时候加载的

    版权声明:本文为博主汪子熙原创文章,未经博主允许不得转载。 https://jerry.bl...

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券