题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个整数数组，请给出一个子数组（连续且至少包含一个数字）求其中子数组和最大值。

思路分享

  • 两个方法：

  • 第一个是求其前缀和，然后转化为贪心的求子数组和问题；

  • 第二个是动态规划，把求前 i 个元素的最大子数组和转化为求前 i-1 个元素的，其中状态转移为 f[i] = max(0, f[i-1])+nums[i]，原因是如果前 i-1 个的最大子数组和为负数，那么还不如另起炉灶从零开始。

    https://leetcode.cn/problems/maximum-subarray/solutions/2533977/qian-zhui-he-zuo-fa-ben-zhi-shi-mai-mai-abu71/

  • 注意，动态规划所得 f 的最后一个数字并非答案，因为这样的状态转移方程要求第 i 处必须有 nums 的第 i 个元素，所以得看 f 中最大的值。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 动态规划
        n = len(nums)
        f = [0] * n
        f[0] = nums[0]
        for i, num in enumerate(nums):
            if i == 0:
                continue
            f[i] = max(0, f[i-1]) + num
        # print(f)
        return max(f)


        # 通过前缀和转为贪心
        # n = len(nums)
        # pre_sum = [nums[0]] * (n)
        # for i in range(1, n):
        #     pre_sum[i] = pre_sum[i-1] + nums[i]

        # ans = -inf
        # min_pre = 0
        # for num in pre_sum:
        #     ans = max(ans, num-min_pre)
        #     if num < min_pre:
        #         min_pre = num
        # return ans