【每日一题20221011】最大子序列总和

兴趣爱好交流 每日一题
1

子序列最大和，包括在一个数组或整数列表中查找连续子序列的最大和：

最大序列（[-2，1，-3，4，-1，2，1，-5，4]）
应为6:
[4，-1，2，1]

简单的情况是，列表仅由正数组成，最大和是整个数组的和。如果列表仅由负数组成，则返回0。

空列表被视为最大和为零。请注意，空列表或数组也是有效的子列表/子数组。’

题目难度：简单
题目来源： Maximum subarray sum | Codewars 

def max_sequence(arr: list) -> int:
    # your code here

assert max_sequence([]) == 0
assert max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_sequence([-2, -1, -3, -4, -1, -2, -1, -5, -4]) == 0
assert max_sequence([7, 4, 11, -11, 39, 36, 10, -6, 37, -10, -32, 44, -26, -34, 43, 43]) == 155
assert max_sequence([-6, -3, 27, -22, 3, 8, 19, -7, -26, -30, -3, -26, 22, 25, -26, 27, 4, -24, -7, 20, 20, 20, 9, -23, -26, -27, -12, 0, 1, 26, -19, -1, -15, -16, 1, 25, 4, -7, 27, 4, -22, -10, 23, 4, 2, -29, 0, -12, -21, 7]) == 90
2 

def max_sequence(arr: list) -> int:
    # your code here
    l = len(arr)
    result = 0
    if l == 0:
        result = 0
    else:
        for i in range(1, l+1):  # 子列表长度
            for j in range(0,l-i+1):  # 子列表第一个元素在原始列表中的下标
                s = 0
                for k in range(j,j+i):
                    s = s + arr[k]
                if s > result:
                    result = s
    return result

assert max_sequence([]) == 0
assert max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_sequence([-2, -1, -3, -4, -1, -2, -1, -5, -4]) == 0
assert max_sequence([7, 4, 11, -11, 39, 36, 10, -6, 37, -10, -32, 44, -26, -34, 43, 43]) == 155
assert max_sequence([-6, -3, 27, -22, 3, 8, 19, -7, -26, -30, -3, -26, 22, 25, -26, 27, 4, -24, -7, 20, 20, 20, 9, -23, -26, -27, -12, 0, 1, 26, -19, -1, -15, -16, 1, 25, 4, -7, 27, 4, -22, -10, 23, 4, 2, -29, 0, -12, -21, 7]) == 90
3 
def max_sequence(arr):
    if not arr: return 0
    dp=[0 for i in range(len(arr))]
    dp[0]=arr[0]
    for i in range(1,len(arr)):
        dp[i]=max(arr[i],dp[i-1]+arr[i])
    return 0 if max(dp)<0 else max(dp)
4

想到两种：
一 -》

def max_sequence(arr: list) -> int:
    l = len(arr)
    max_num = 0
    if l == 0:
        return max_num
    else:
        for i in range(l-1):
            for j in range(i+1,l):
                x= sum(arr[i:j]) + arr[j]
                if x > max_num:
                    max_num = x

        return max_num

二-》

def max_sequence(arr: list) -> int:
    l = len(arr)
    max_num = 0
    if l == 0:
        return max_num
    else:
        for i in range(l-1):
            if arr[i] < 0:
                continue
            j = l - 1
            while i < j:
                if arr[j] < 0:
                    j -= 1
                    continue
                x = sum(arr[i:j]) + arr[j]
                if x > max_num:
                    max_num = x
                j -= 1
        return max_num
5 
def max_sequence(arr: list) -> int:
    m = 0
    n = 0
    i = 0
    for i in range(len(arr)):
        if arr[i] > 0:
            break
    for j in range(i,len(arr)):
        if n + arr[j] >= 0:
            n += arr[j]
            m = max(m,n)
        else:
            n = 0
    return m
6 
def max_sequence(arr: list) -> int:
    arr_len = len(arr)
    my_list = []
    if arr_len == 0:  # 如果是空列表，返回0
        return 0
    else:
        for i in range(0, arr_len):
            for j in range(i + 1, arr_len + 1):
                my_list.append(sum(arr[i:j]))  # 通过sum求切片和，列举出所有情况
                my_list.sort(reverse=True)  # 对切片和所有情况排序，找最大值
        if my_list[0] <= 0:  # 如果最大值小于等于0（全负数情况），返回0
            return 0
        else:
            return int(my_list[0])  # 输出最大值


assert max_sequence([]) == 0
assert max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_sequence([-2, -1, -3, -4, -1, -2, -1, -5, -4]) == 0
assert max_sequence([7, 4, 11, -11, 39, 36, 10, -6, 37, -10, -32, 44, -26, -34, 43, 43]) == 155
assert max_sequence(
    [-6, -3, 27, -22, 3, 8, 19, -7, -26, -30, -3, -26, 22, 25, -26, 27, 4, -24, -7, 20, 20, 20, 9, -23, -26, -27, -12,
     0, 1, 26, -19, -1, -15, -16, 1, 25, 4, -7, 27, 4, -22, -10, 23, 4, 2, -29, 0, -12, -21, 7]) == 90
7 
def max_sequence(arr: list) -> int:
    prenum = 0
    finnum = 0
    for i in arr:
        if prenum > finnum:
            finnum = prenum
        if i <= 0:
            if prenum + i <= 0:
                    prenum = 0
            else:
                prenum += i
        else:
            prenum += i
    if prenum > finnum:
        finnum = prenum
    return finnum
8 
def max_sequence(arr: list) -> int:
    max_sum=0
    if arr==[]:
        return 0
    elif max(arr)<0:
        return 0
    else:
        left_setp=0
        while left_setp<len(arr):
            right_setp=left_setp+1
            while right_setp<=len(arr):
                if max_sum<sum(arr[left_setp:right_setp+1]):
                    max_sum=sum(arr[left_setp:right_setp+1])
                right_setp+=1
            left_setp+=1
        return max_sum

assert max_sequence([]) == 0
assert max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_sequence([-2, -1, -3, -4, -1, -2, -1, -5, -4]) == 0
assert max_sequence([7, 4, 11, -11, 39, 36, 10, -6, 37, -10, -32, 44, -26, -34, 43, 43]) == 155
assert max_sequence([-6, -3, 27, -22, 3, 8, 19, -7, -26, -30, -3, -26, 22, 25, -26, 27, 4, -24, -7, 20, 20, 20, 9, -23, -26, -27, -12, 0, 1, 26, -19, -1, -15, -16, 1, 25, 4, -7, 27, 4, -22, -10, 23, 4, 2, -29, 0, -12, -21, 7]) == 90