MarsCode-贪心的小包

贪心的小包

问题描述

小包非常喜欢吃甜点，他收到了一次性送来的 NN 个甜点，每个甜点都有一个对应的喜爱值。

但是这还不够！小包让小哥连续送来了 MM 次相同的 NN 个甜点，并将这些甜点首尾相接排成一排。

现在，小包面前有 (N×M)(N×M) 个排成一排的甜点，小包希望从中选择一段连续的甜点，使得这段甜点的总喜爱值最大化。

注意：尽管小包喜欢甜食，但有些甜点可能不合口味，导致其喜爱值为负数。小包至少要选择一个甜点来满足他对甜点的贪心。

输入参数

• 整数 ( N )：表示每次送来的甜点数量。
• 整数 ( M )：表示送来的次数。
• 数组 data：长度为 ( N )，表示每个甜点的喜爱值。

返回结果

• 一个整数，表示在 N×MN×M 个甜点中可以选择的连续甜点段的最大总喜爱值。

---

测试样例

样例1：

输入：N = 5 ,M = 1 ,data = [1, 3, -9, 2, 4]
输出：6
解释：选择甜点 [2, 4]，最大总喜爱值为 6

样例2：

输入：N = 5 ,M = 3 ,data = [1, 3, -9, 2, 4]
输出：11
解释：排列后甜点为 [1, 3, -9, 2, 4, 1, 3, -9, 2, 4, 1, 3, -9, 2, 4]。
选择 [2, 4, 1, 3, -9, 2, 4, 1, 3] 这段连续甜点，最大总喜爱值为 11

解答

动态规划（复杂度较高）

def solution(N, M, data):
    # Edit your code here
    extended_data = data * M
    # 求最大连续子数组和 O(N*M)^2
    lenth = len(extended_data)
    dp = [[0 for _ in range(lenth)] for _ in range(lenth)]
    for i in range(lenth):
        dp[i][i] = extended_data[i]
    for i in range(lenth):
        for j in range(i+1, lenth):
            dp[i][j] = dp[i][j-1] + extended_data[j]
    ans = -float('inf')
    for i in range(lenth):
        for j in range(i, lenth):
            if ans < dp[i][j]:
                ans = dp[i][j]
    return ans


if __name__ == "__main__":
    # Add your test cases here
    print(solution(5, 1, [1, 3, -9, 2, 4]) == 6)
    print(solution(5, 3, [1, 3, -9, 2, 4]) == 11)