LintCode 41. 最大子数组
题目描述
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
子数组最少包含一个数。
挑战：要求时间复杂度为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)
