首页 > 代码库 > 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 简单级题目 最小子数组和、最大子数组和