#53 Maximum Subarray ——Top 100 Liked Questions

深藏阁楼爱情的钟 2022-01-30 05:13 135阅读 0赞

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

**Example:**

Input: [-2,1,-3,4,-1,2,1,-5,4],
    Output: 6
    Explanation: [4,-1,2,1] has the largest sum = 6.

**Follow up:**

If you have figured out the O(*n*) solution, try coding another solution using the divide and conquer approach, which is more subtle

> """
> 
> 第一次：居然会想到用动态规划！感觉自己进步了hhhh。思路：定义dp，dp\[i\]=dp\[i-1\]+nums\[i\]，如果和较nums\[i\]增大了，则对应位置保存，如果减小了，对应位置为nums\[i\]的值不变，最后返回dp中的最大值
> 
> """
> 
>     class Solution(object):
>         def maxSubArray(self, nums):
>             """
>             :type nums: List[int]
>             :rtype: int
>             """
>             if not nums:
>                 return None
>             L = len(nums)
>             dp = [0] * L
>             dp[0] = nums[0]
>             for i in range(1, L):
>                 if nums[i] + dp[i - 1] > nums[i]:
>                     dp[i] = nums[i] + dp[i - 1]
>                 else:
>                     dp[i] = nums[i]
>             return max(dp)
> 
>   
> """
> 
> Runtime: 48 ms, faster than 57.44% of Python online submissions for Maximum Subarray.
> 
> Memory Usage: 12.7 MB, less than 10.39% of Python online submissions for Maximum Subarray.
> 
> """

发表评论取消回复

表情：

评论列表（有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode53——Maximum Subarray

LeetCode53——Maximum Subarray 题意：就是经典的动态规划问题。这里直接给出公式： dp\[i\]表示以nums\[i\]结尾的最大子序列和

梦里梦外;/ 2022年08月09日 12:56/ 0 赞/ 134 阅读

相关 leetcode 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has

比眉伴天荒/ 2022年07月28日 01:05/ 0 赞/ 167 阅读

相关【LeetCode】53. Maximum Subarray

53. Maximum Subarray Find the contiguous subarray within an array (containing at lea

布满荆棘的人生/ 2022年07月26日 05:14/ 0 赞/ 180 阅读

相关 [leetcode]: 53. Maximum Subarray

1.题目 Find the contiguous subarray within an array (containing at least one number) wh

Bertha 。/ 2022年06月15日 02:37/ 0 赞/ 164 阅读

相关 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which

浅浅的花香味﹌/ 2022年06月02日 12:19/ 0 赞/ 175 阅读

相关 53. Maximum Subarray

Given an integer array `nums`, find the contiguous subarray (containing at least one num

我会带着你远行/ 2022年04月21日 23:46/ 0 赞/ 177 阅读

相关 #53 Maximum Subarray ——Top 100 Liked Questions

Given an integer array `nums`, find the contiguous subarray (containing at least one num

深藏阁楼爱情的钟/ 2022年01月30日 05:13/ 0 赞/ 136 阅读

相关 #72 Edit Distance——Top 100 Liked Questions

Given two words word1 and word2, find the minimum number of operations required to conve

妖狐艹你老母/ 2022年01月29日 03:09/ 0 赞/ 230 阅读

相关 #78 Subsets ——Top 100 Liked Questions

Given a set of distinct integers, nums, return all possible subsets (the power set). No

本是古典何须时尚/ 2022年01月27日 02:09/ 0 赞/ 243 阅读

相关 letecode [53] - Maximum Subarray

Given an integer array `nums`, find the contiguous subarray (containing at least one num

亦凉/ 2021年11月04日 11:06/ 0 赞/ 234 阅读