【每日一题20220906】给定多个范围索引，计算目标列表最大总和值

兴趣爱好交流 每日一题
1

:mage: 给定一个整数列表，对于列表中的每对整数，计算指数和（包括两者）之间的值的总和，并返回最大的结果和。

例

A = [1, -2, 3, 4, -5, -4, 3, 2, 1]
ranges = [(1, 3), (0, 4), (6, 8)]

result = 6
  • 因为总和是ranges[0] = (1, 3) A[1] + A[2] + A[3] = 5
  • 因为总和是ranges[1] = (0, 4) A[0] + A[1] + A[2] + A[3] + A[4] = 1
  • 因为总和是ranges[2] = (6, 8) A[6] + A[7] + A[8] = 6
  • 最大总和是6

备注

  • 范围列表永远不会是空的;
  • 这是一个挑战版本，您应该实现一个有效的算法以避免超时

题目难度：一般
题目来源：https://www.codewars.com/kata/583d171f28a0c04b7c00009c

def max_sum(a: list, ranges: list) -> int:
    # your code here

assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 3), (0, 4), (6, 8)]) == 6
assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 3)]) == 5
assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 4), (2, 5)]) == 0
assert max_sum([4, 77, 17, 6, -74, -26, 95, 99, -21, -93, 38, 36, 64, 78, 19, 73, -26, -94, 0, 1], [(2, 15), (0, 8), (8, 17), (1, 19), (5, 14), (1, 19), (5, 16), (1, 13), (8, 11), (0, 19), (3, 15), (4, 18), (10, 17), (5, 17), (2, 18), (3, 19), (5, 18), (1, 19), (0, 17), (8, 11)]) == 336
# 大数据的随机测试可以点击源题进行测试，列表长度达100000
2 
def max_sum(a: list, ranges: list) -> int:
    lresult = []
    for i in ranges:
        sum = 0
        for j in range(i[0], i[-1] + 1):
            sum += a[j]
        lresult.append(sum)
    return max(lresult)
3

方法一：

def max_sum(a: list, ranges: list) -> int:
    """
    给定多个范围索引，计算目标列表最大总和值
    :param a: 目标列表
    :param ranges: 范围
    :return: 最大总和值
    """
    def gen_sum(arr: list, ran: list):
        for rang in ranges:
            # 根据切片对a求和
            yield sum(arr[rang[0]:rang[1]+1])

    return max(gen_sum(a, ranges))


assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 3), (0, 4), (6, 8)]) == 6
assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 3)]) == 5
assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 4), (2, 5)]) == 0
assert max_sum([4, 77, 17, 6, -74, -26, 95, 99, -21, -93, 38, 36, 64, 78, 19, 73, -26, -94, 0, 1], [(2, 15), (0, 8), (8, 17), (1, 19), (5, 14), (1, 19), (5, 16), (1, 13), (8, 11), (0, 19), (3, 15), (4, 18), (10, 17), (5, 17), (2, 18), (3, 19), (5, 18), (1, 19), (0, 17), (8, 11)]) == 336
4

方法二：

def max_sum(a: list, ranges: list) -> int:
    """
    给定多个范围索引，计算目标列表最大总和值
    :param a: 目标列表
    :param ranges: 范围
    :return: 最大总和值
    """
    # 使用生成器推导式
    gen_sum = (sum(a[item[0]:item[1]+1]) for item in ranges)

    return max(gen_sum)


assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 3), (0, 4), (6, 8)]) == 6
assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 3)]) == 5
assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 4), (2, 5)]) == 0
assert max_sum([4, 77, 17, 6, -74, -26, 95, 99, -21, -93, 38, 36, 64, 78, 19, 73, -26, -94, 0, 1], [(2, 15), (0, 8), (8, 17), (1, 19), (5, 14), (1, 19), (5, 16), (1, 13), (8, 11), (0, 19), (3, 15), (4, 18), (10, 17), (5, 17), (2, 18), (3, 19), (5, 18), (1, 19), (0, 17), (8, 11)]) == 336
5

image
image1707×761 66.5 KB

6 
def max_sum(a: list, ranges: list) -> int:
    res_list=[]
    for i in ranges:
        res_list.append(sum([a[j] for j in range(i[0],i[1]+1)]))
    return max(res_list)

assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 3), (0, 4), (6, 8)]) == 6
assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 3)]) == 5
assert max_sum([1, -2, 3, 4, -5, -4, 3, 2, 1], [(1, 4), (2, 5)]) == 0
assert max_sum([4, 77, 17, 6, -74, -26, 95, 99, -21, -93, 38, 36, 64, 78, 19, 73, -26, -94, 0, 1], [(2, 15), (0, 8), (8, 17), (1, 19), (5, 14), (1, 19), (5, 16), (1, 13), (8, 11), (0, 19), (3, 15), (4, 18), (10, 17), (5, 17), (2, 18), (3, 19), (5, 18), (1, 19), (0, 17), (8, 11)]) == 336