2021秋招字节跳动测试工程师 笔试

求最大子序列的和

题目描述： 输入M代表原始的一个序列的长度，输入N代表代表复制M的次数，组成一个新的长序列，顺序不能改变。从新的长序列中找出连续的子序列，使得这个子序列的和最大。

示例

输入：

N = 5 M = 3
arr = [1,3,-9,2,4]

输出：

11

其中，将arr复制3次，得到新的长序列为：

[1, 3, -9, 2, 4, 1, 3, -9, 2, 4, 1, 3, -9, 2, 4]

代码：

class Solution:
    def xulie(self, N, M, num):
        t = num[:]
        for i in range(M - 1):
            num.extend(t)
        print(num)
        max_sum = num[0]
        a_sum = max_sum
        for i in range(1, len(num)):
            a = num[i]
            a_sum = max(a, a_sum + a)
            max_sum = max(max_sum, a_sum)
        return max_sum

if __name__ == '__main__':
    print('N = ')
    N = int(input())
    print('M = ')
    M = int(input())
    #arr = input("")
    #num = [int(n) for n in arr.split()]
    num = [1,3,-9,2,4,]
    w = Solution()
    res = w.xulie(N, M, num)
    print('result = ', res)