数组求分段最小和

某次笔试,但是由于笔试时间冲突,只得快速解决问题,没来得及考虑到性能优化,当时只过了小部分的测试用例,再思考效率影响的地方,重写一下。

# -*- coding:utf-8 -*-
# author: DYBOY
# time: 2019-9-20 12:41:32
# desc: 求给出数组中一定长区间的和最小,输出最小和的值

import sys

def mysum(arr, start, num):
    return sum(arr[start: start+num])

# 第二种方法,求出每段的和,然后比较获得最小和值
def list_segament_sum(arr, num):
    sum_arr = [sum(arr[0:num])]
    for i in range(num, len(arr)):
        sum_arr.append(sum_arr[i-num] + arr[i] - arr[i-num])
    return min(sum_arr)

if __name__ == '__main__':
    line1 = input()
    n, m = (line1.strip()).split()
    m = int(m)
    line2 = input()
    line2 = list( map(int, line2.strip().split()))
    min_sum = 99999                   # 记录最小和值
    for i in range(len(line2) - m):
        temp_sum = mysum(line2, i, m)
        if temp_sum < min_sum:
            min_sum = temp_sum
    print(min_sum)
下一篇
CSRF浅谈
发表评论 / Comment

用心评论~