首页 > 代码库 > LintCode Python 简单级题目 最小子数组和、最大子数组和
LintCode Python 简单级题目 最小子数组和、最大子数组和
题目1 最小子数组
描述：
给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。
注意事项
子数组最少包含一个数字
您在真实的面试中是否遇到过这个题？
Yes
样例
给出数组[1, -1, -2, 1]，返回 -3
标签
LintCode 版权所有 子数组 贪心 数组
题目2 最大子数组
描述：
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
注意事项
子数组最少包含一个数
您在真实的面试中是否遇到过这个题？
Yes
样例
给出数组[?2,2,?3,4,?1,2,1,?5,3]，符合要求的子数组为[4,?1,2,1]，其最大和为6
挑战
要求时间复杂度为O(n)
标签
贪心 枚举法 数组 LintCode 版权所有 子数组 领英
题目分析：
题目1求最小子数组和，题目没有写要求算法复杂度，可以考虑Python的数组切片功能，只能获取子数组，然后求和，获取最小值
通过动态规划，依次获取nums[i:j]的子数组和，算法复杂度O(n*logn)
def minSubArray(nums):
max = min = sum(nums)
maxList = minList = nums
n = len(nums)+1
for i in range(n+1):
for j in range(i+1,n+1):
sonList = nums[i:j]
Sum = sum(sonList)
if Sum >= max:
max = Sum
maxList = sonList
elif Sum < min:
min = Sum
minList = sonList
print maxList,sum(maxList)
print minList, sum(minList)
题目二要求算法复杂度O(n)，上诉动态规划算法不符合要求，使用贪心算法：
class Solution:
"""
@param nums: A list of integers
@return: An integer denote the sum of maximum subarray
"""
def maxSubArray(self, nums):
# write your code here
n = len(nums)
maxSum = sum(nums)
curSum = 0
for i in range(n):
# 从i开始求和，如果当前和大于maxSum,则赋值给maxSum
curSum += nums[i]
if curSum > maxSum:
maxSum = curSum
# 前面的和如果已经小于0了，那么加上下一个元素值，肯定是小于下一个元素值
# 所以如果前面加起来的值小于0了，则舍弃前面的和，从下一位开始继续求和
if curSum < 0:
curSum = 0
return maxSum
同理，最小子数组也可以使用贪心算法，缺点是无法获取到最小子串，只能获取其和。
class Solution:
"""
@param nums: a list of integers
@return: A integer denote the sum of minimum subarray
"""
def minSubArray(self, nums):
# write your code here
n = len(nums)
minSum = sum(nums)
curSum = 0
for i in range(n):
# 从i开始求和，如果当前和小于于minSum,则赋值给minSum
curSum += nums[i]
if curSum < minSum:
minSum = curSum
# 前面的和如果已经大于0了，那么加上下一个元素值，肯定是大于下一个元素值
# 所以如果前面加起来的值大于0了，则舍弃前面的和，从下一位开始继续求和
if curSum > 0:
curSum = 0
return minSum
LintCode Python 简单级题目 最小子数组和、最大子数组和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。