leetcode day11

1.题目描述

2.代码构思（debug）

方法1:贪心法
若当前指针所指元素之前的和小于0，则丢弃之前的子序列和
curnum存储前n个数字的和，如果之和小于等于0，则+nums[i+1]肯定小于nums[i]
class Solution:

def maxSubArray(self, nums: List[int]) -> int:
    len1 = len(nums)
    #设置边界条件
    if len1 == 0:
        return -2147483648

	#初始值设为列表第一个元素
    maxres = curnum = nums[0]
    for i in range(1,len1):
        curnum = max(nums[i],curnum+nums[i])
        maxres = max(maxres,curnum)
   
    return maxres
1
2
3
4
5
6
7
8
9
10
11
12
13

方法2

使用动态规划
若前一个值大于0，则将其加到当前元素上,然后返回nums中最大值即可
class Solution:

def maxSubArray(self, nums: List[int]) -> int:
    len1 = len(nums)
    if len1 == 0:
        return -2147483648
    for i in range(1,len1):
        if nums[i - 1] > 0:
            nums[i] += nums[i - 1]

    return max(nums)
1
2
3
4
5
6
7
8
9