【每日一题0816】子列表极值

兴趣爱好交流 每日一题
1

:woman_mage:已知一个由数字的列表，请编写一个python函数，求出该列表中总和最大的子列表的和值。如果列表元素全为负数则返回0 。

示例：
输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4] ，输出：6 。
因为最大和值子列表是[4, -1, 2, 1] 。

题目难度：中等
题目来源：codewars

def max_sequence(nums:list) -> int:
    pass
  
assert max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_sequence([1, 2, 3, 4, 100]) == 110
assert max_sequence([-1, -2, -3, -4, -100]) == 0
assert max_sequence([]) == 0
2 

def max_sequence(nums: list) -> int:
    if nums is None or nums == []:
        return 0
    if max(nums) < 0:
        return 0
    res = []

    def fs(tmp_nums, left, right):
        tmp = []
        max_sum = tmp_nums[left] + tmp_nums[right]
        sums = tmp_nums[left] + tmp_nums[right]
        while right < len(tmp_nums) - 1:
            right += 1
            sums += tmp_nums[right]
            if sums >= max_sum:
                max_sum = sums
                continue
            else:
                tmp.append([tmp_nums[left:right], max_sum])
                break
        else:
            tmp.append([tmp_nums[left:right], max_sum])
        return tmp

    for i in range(len(nums) - 1):
        res.append(fs(nums, i, i + 1))
    return [i for i in res if i[0][1] == max([j[0][1] for j in res])][0][0][1]


assert max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_sequence([1, 2, 3, 4, 100]) == 110
assert max_sequence([-1, -2, -3, -4, -100]) == 0
assert max_sequence([]) == 0
3 
def max_sequence(nums:list):
    res=[]
    if len(nums)==0:
        return 0
    count=0
    for i in nums:
        if i<0:
            count=count+1
    if count==len(nums):
        return 0
    for i in range(len(nums)):
        if nums[i]<0:
            continue
        sum=nums[i]
        for j in range(i+1,len(nums)):
            sum=sum+nums[j]
            res.append(sum)
    return max(res)
4

时间复杂度有点高，等更优解

5 
# 动态规划法
def maxSubArray(nums: list) -> int:
    if nums is None or len(nums) == 0:
        return 0
    if max(nums) < 0:
        return 0
    for i in range(1, len(nums)):
        print(nums[i])
        nums[i] += max(nums[i - 1], 0)
        print(nums[i])
    return max(nums)

详解可以看https://ceshiren.com/t/topic/13894

# 贪心法
# 从左往右连续加，更新最大值，若 总和小于0，则 断掉 重新从下一个开始计算
def tanxin_maxsub_array(nums: list) -> int:
    if nums is None or len(nums) == 0:
        return 0
    if max(nums) < 0:
        return 0
    all_sum: int = 0
    all_max: int = 0
    for i in nums:
        all_sum += i
        all_max = max(all_sum, all_max)
        if all_sum < 0:
            all_sum = 0
    return all_max

详解见https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/

6 
def max_sequence(nums: list) -> int:
    if len(nums) == 0 :
        return 0
    if max(nums) < 0 :
        return 0
    item_max = nums[0]
    result = nums[0]
    for item in range(1,len(nums)):
        item_max = max(nums[item],item_max+nums[item])
        result = max(result,item_max)
    return result

assert max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_sequence([1, 2, 3, 4, 100]) == 110
assert max_sequence([-1, -2, -3, -4, -100]) == 0
assert max_sequence([]) == 0