题目描述

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

子数组最少包含一个数。

挑战：要求时间复杂度为O(n)

---

样例

输入：[−2,2,−3,4,−1,2,1,−5,3]

输出：6

解释：符合要求的子数组为[4,−1,2,1]，其最大和为 6。

输入：[1,2,3,4]

输出：10

解释：符合要求的子数组为[1,2,3,4]，其最大和为 10。

---

思路

这题挺简单，但是直觉告诉我面试时被考到的概率不会低（CW的第六感？），你当然不能用暴力法去做，O(n^2)的复杂度会让面试官很难受，对于这种容易题，面试官通常会要求你用多种解法写出来。

1、prefix sum

你需要拥有这种信念——最大的局部和 = 最大前缀和 - 最小前缀和，这种解法的本质就在这里，明确了这点，代码也就几行。

2、greedy

设置2个变量，分别记录 以位置i结尾的最大前缀和 以及 全局最大和。每次遍历过程中，前者都要和0进行比较，因为如果是负数和，那么加到下个数上势必会更小（与下个数本身相比），所以可以直接放弃这个负数和，将其置0，重新从下个数开始累加。

3、dp

dp[i]记录以i结尾可获得的最大局部和，更新方式为：dp[i] += max(0, dp[i-1])，最后返回max(dp)即为所求。

---

代码

1、prefix sum

import sys

class Solution:

    """

    @param nums: A list of integers

    @return: A integer indicate the sum of max subarray

    """

    def maxSubArray(self, nums):

        if len(nums) == 1:

            return nums.pop()

        max_sum = -sys.maxsize

        prefix_sum = 0

        min_prefix_sum = 0

        for n in nums:

            prefix_sum += n

            max_sum = max(max_sum, prefix_sum - min_prefix_sum)

            min_prefix_sum = min(min_prefix_sum, prefix_sum)

        return max_sum

2、greedy

i).

import sys

class Solution:

    """

    @param nums: A list of integers

    @return: A integer indicate the sum of max subarray

    """

    def maxSubArray(self, nums):

        if len(nums) == 1:

            return nums.pop()

        max_local_sum = 0

        max_global_sum = -sys.maxsize

        for n in nums:

            max_local_sum += n

            max_global_sum = max(max_global_sum, max_local_sum)

            max_local_sum = max(0, max_local_sum)

        return max_global_sum

ii).

import sys

class Solution:

    """

    @param nums: A list of integers

    @return: A integer indicate the sum of max subarray

    """

    def maxSubArray(self, nums):

        if len(nums) == 1:

            return nums.pop()

        max_local_sum = 0

        max_global_sum = -sys.maxsize

        for n in nums:

            # 局部最大和指遍历到当前数字时能获得的最大和

            # 若之前的所有数字和为负数

            # 那么加到当前数字上势必更小

            # 于是此时的局部最大和就是当前数字

            max_local_su2\m = max(max_local_sum + n, n)

            # 每次都将局部最大和与全局比较

            # 从而记录到全局最大和

            max_global_sum = max(max_global_sum, max_local_sum)

        return max_global_sum

3、dp

classSolution: """

    @param nums: A list of integers

    @return: A integer indicate the sum of max subarray

    """    defmaxSubArray(self, nums):        if len(nums) == 1:

            return nums.pop()

        for i in range(1, len(nums)):

            nums[i] += max(nums[i - 1], 0)

        return max(nums)