Python——LeetCode刷题——【53. 最大子数组和】

题目描述：

解题思路：

方法一：贪心策略

遍历列表，从list第0位开始，只要当前序列和＜0，就舍弃前面全部序列。如果前面序列和>0,将当前值累加上去，即使当前值为负，因为要保证连续子序列这个条件。如果当前序列和大于了最大序列和，则进行替换。遍历完整个list即可找出最大子序列和。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_sum = -10000
        max_sum = -10000
        for i in nums:
            # 前面序列为负时，进行舍弃
            if current_sum < 0:
                current_sum = i
            # 不为负的话，进行累加
            else:
                current_sum += i
            if current_sum > max_sum:
                max_sum = current_sum
        return max_sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二：动态规划

新建一个list,将原来list中的值全部copy到新的list中。新list的第0个值不变，第1个值开始，如果当前位置前面的值大于0，则与nums当前位置值相加。按此策略遍历完旧list,
然后返回新list中的最大值，即为最大子序列和。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        i = 1
        # 新list
        temp = nums
        temp[0] = nums[0]
        while(i<len(nums)):
            # 前一个位置的值小于0就不改变当前位置值
            if nums[i-1] < 0:
                temp[i] = nums[i]
                i += 1
            # 前面的值不为负，就进行累加
            else:
                temp[i] += nums[i-1]
                i += 1
        # 返回新list中的最大值
        return max(temp)            


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19